문제 정보
1016번: 제곱 ㄴㄴ 수
어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수
www.acmicpc.net
핵심
에라토스테네스의 체 알고리즘을 활용하여 해당 범위 내에 있는 제곱 ㄴㄴ 수를 찾아낸다
여기서 제곱 ㄴㄴ 수란, 1보다 큰 제곱수로 나누어 떨어지지 않는 수이다.
1부터 10까지의 제곱 ㄴㄴ 수를 알아보면
1 2 3 (4) 5 6 7 (8) (9) 104(2의 제곱) 으로 나누어지는 4, 8은 제곱 ㄴㄴ 수가 아니고,
9(3의 제곱) 으로 나누어지는 9는 제곱 ㄴㄴ 수가 아니므로 이를 제외한 나머지 숫자들이 제곱 ㄴㄴ 수가 된다
일반적인 에라토스테네스의 체 알고리즘을 사용하여 풀이한다면, 조건에서 숫자의 크기가 너무 크기 때문에 시간 초과가 발생할 가능성이 매우 크다
따라서 이러한 조건을 알맞게 잘 설정해주는 것이 중요하다
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* 백준 1016 제곱 ㄴㄴ수 에라토스테네스의 체? -> 저 개수만큼의 배열 생성 불가함 그럼 어떻게 풀이할까? 제곱수로 나누어 떨어지는지?
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
long min = Long.parseLong(st.nextToken());
long max = Long.parseLong(st.nextToken());
// 1, 2, 3 까지 제곱 ㄴㄴ수 -> false
// 1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17 ...
// 4, 8, 12, 16 ... (4의 배수들)
// 제곱수로 나누어 떨어지는지 ?
// 4(2^2) 9(3^2) 16(4^2) 25(5^2) 의 배수들을 파악하면 된다
long size = max - min + 1;
boolean[] isDivide = new boolean[(int) size];
// 각 인덱스와 숫자의 관계는? index + min = number
for (long i = 2; i < Math.pow(max, 0.5) + 1; i++) {
// long j = min / i + 1;
long j = min / (i * i);
while (i * i * j <= max) {
long tmp;
tmp = i * i * j;
if (tmp >= min && tmp <= max) {
tmp -= min;
if (!isDivide[(int) tmp]) {
isDivide[(int) tmp] = true;
size--;
}
}
j += 1;
}
}
System.out.println(size);
}
}
문제의 조건에서 1 <= min <= 1,000,000,000,000, min <= max + 1,000,000 으로 주어졌기 때문에 int 자료형은 사용할 수 없고,
범위가 더 넓은 long을 사용해 주었다.
코드에서 long j = min / (i * i); 로 잡은 이유는, 반복 횟수를 최소화하기 위함이었는데
j=1 부터 시작한다고 하더라도 어차피 해당 숫자의 범위 안에 들어와야 하기 때문에,
만약 min = 1조, max = 1조 1백만 이라면? 조건인 while(i*i*j <= max) 를 만족하기 때문에 j+=1 을 해주는 연산을 계속 반복할 것이고,
이는 매우 비효율적인 작업이다
마지막으로 size 변수를 1씩 빼주면서 결과를 출력한 이유는,
제곱수로 나누어 떨어진다면 isDivide의 해당 인덱스(idx-min) 은 true 값이 될 것이며 결론적으로 제곱수로 나누어 떨어진다면,
한번만 이 작업이 수행될 것이고 전체 수에서 제곱수로 나누어 떨어지는 수의 개수를 빼 준다면,
우리가 원하는 답인 제곱 ㄴㄴ 수의 개수를 구할 수 있을 것이다
고찰
시간이 조금 걸려서 문제를 풀이하였지만, 결국 혼자서 풀이를 완료하였다!
가장 중요한 것은 아무래도 무턱대고 코드를 작성하기 보다는, 동작 과정을 생각하고 그려보면서 어느정도 갈피가 잡혔을 때 코드를 작성하는 것이 문제를 빠르게 풀이할 수 있는 방법이라고 다시금 느꼈다!
참고
백준 알고리즘: 1978번 소수 찾기
문제 정보 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 핵심 소수를 구하는 방법을 알면 된다
blog.dduneon.me
댓글