[백준 / JAVA] 백준 알고리즘 1016번 제곱 ㄴㄴ수

만약, min = 1,000,000,000,000(1조)이고, max = 1,000,000,500,000(1조 50만)일 경우, 실제로 비교해야할 구간은 약 50만개밖에 되지 않는다. 이 구간을 배열 $A$ 로 표시하면 $A[0] = 1,000,000,000,000\text{(min)}$ 가 된다. 즉, $A[i] = i + \text{min}$ 으로 다뤄야한다.

제곱수의 배수를 제외해야한다는 점에서 소수의 배수를 제외하여 소수를 판별하는 에라토스 테네스의 체의 개념와 매우 흡사하다. 즉, 에라토스 테네스의 체 알고리즘에서 소수가 아닌 제곱수의 배수를 판별하게끔 살짝 변형시켜주면 된다.

전체 소스

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

/**
 * 백준 전체 1016 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/23/a1016">1016 풀이</a>
 * @since 2021.06.23 Fri 00:22:31
 */
public class Main
{
	// 최소값
	private static long min;
	
	// 최대값
	private static long max;
	
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		long[] temp = Arrays.stream(reader.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
		
		min = temp[0];
		max = temp[1];
		
		writer.write(Integer.toString(solve()));
		writer.newLine();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 알고리즘 결과 반환 함수
	 *
	 * @return [int] 제곱수로 나누어 떨어지지 않는 수의 갯수
	 */
	private static int solve()
	{
		int size = 0;
		
		boolean[] isNotPow = eratosthenes();
		
		for (boolean item : isNotPow)
		{
			// 제곱수로 나누어 떨어지지 않는 수일 경우
			if (!item)
			{
				size++;
			}
		}
		
		return size;
	}
	
	/**
	 * 에라토스 테네스의 체 배열 반환 함수
	 * true: 제곱ㄴㄴ수가 아닌 수
	 * false: 제곱ㄴㄴ수
	 *
	 * @return [boolean[]] 에라토스 테네스의 체 배열
	 */
	private static boolean[] eratosthenes()
	{
		int length = (int) (max - min + 1);
		
		boolean[] isNotPow = new boolean[length];
		
		for (long i = 2; i * i <= max; i++)
		{
			long pow = i * i;
			
			long start = min % pow == 0 ? min / pow : (min / pow) + 1;
			
			for (long j = start; j * pow <= max; j++)
			{
				// 제곱수의 배수로 나누어 떨어지므로 제곱ㄴㄴ수가 아님
				isNotPow[(int) (j * pow - min)] = true;
			}
		}
		
		return isNotPow;
	}
}

solve() 메소드는 단순히 갯수를 파악하는 로직이므로 그 의도만 알면 된다. 가장 핵심인 부분은 에라토스 테네스의 체를 변형한 아래 코드다.

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 에라토스 테네스의 체 배열 반환 함수
 *
 * true: 제곱ㄴㄴ수가 아닌 수
 * false: 제곱ㄴㄴ수
 *
 * @return [boolean[]] 에라토스 테네스의 체 배열
 */
private static boolean[] eratosthenes()
{
	int length = (int) (max - min + 1);
	
	boolean[] isNotPow = new boolean[length];
	
	for (long i = 2; i * i <= max; i++)
	{
		long pow = i * i;
		
		long start = min % pow == 0 ? min / pow : (min / pow) + 1;
		
		for (long j = start; j * pow <= max; j++)
		{
			// 제곱수의 배수로 나누어 떨어지므로 제곱ㄴㄴ수가 아님
			isNotPow[(int) (j * pow - min)] = true;
		}
	}
	
	return isNotPow;
}

총 2개의 반복문이 돌아간다. 인덱스는 각각 $i$ , $j$ 다.

$i$ : 제곱수의 제곱근
$j$ : 제곱수의 배수를 구하기 위한 인덱스

1보다 큰 제곱수는 4이므로, 인덱스 $i$ 의 시작값은 2이며, 제곱수인 $i^2$ 의 크기가 max 이하일때 까지 반복한다. 만약, 구간이 10부터 30까지라면, $i$ 는 2(4)부터 5(25)까지 증가할 것이다.

인덱스 $j$ 는 약간 복잡한데, 이는 구간의 존재 때문이다. 기본적으로 에라토스 테네스의 체는 1부터 시작하므로 상관없지만, 해당 문제는 시작값이 1이 아닐 경우가 존재한다.

예를 들어, $i = 2$ 이고 구간이 10 ~ 20까지라고 가정하자. $i^2 = 4$ 이므로 제곱수 4의 배수를 제거해야한다. 만약 평상시처럼 곱셈의 인덱스를 1부터 시작해서 $4 \times 1$ , $4 \times 2$ , $\dots$ 와 같이 시작한다면 문제가 생긴다. 구간은 10부터인데 비해, 10 이하인 4, 8을 제거하게되니 이를 걸러내야한다. 만약 구간이 1000부터 시작이라면 250개의 쓸모없는 연산이 발생한다. 구간이 최대 1조부터 시작할 수 있음을 생각한다면 구간의 시작에 따라 곱셈 인덱스 $j$ 를 적절히 계산해야한다.

$i = 2$ 일 경우, $i^2 = 4$ 이다. 구간의 시작이 10일 경우, 10 이하인 수 $4 \times 1$ , $4 \times 2$ 는 건너뛰므로 곱셈 인덱스 $j$ 는 3부터 시작해야한다.

j_{\text{min}} = \begin{cases} \text{min} \div i^2 \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, (\text{min} \,\,\, \% \,\,\, i^2 == 0)\\ (\text{min} \div i^2) + 1 \,\,\, (\text{min} \,\,\, \% \,\,\, i^2 \,\,\, != 0) \end{cases}

즉, 곱셈 인덱스 $j$ 의 시작값의 일반식은 위와 같다.

$\text{제곱수의 배수} = j \times i^2 \,\,\, (j = 1, 2, 3, \dots)$ 이므로, 해당값을 모두 제외하면 된다. 단, $j \times i^2$ 는 실제 값이므로, 배열의 인덱스는 $(j \times i^2) - \text{min}$ 이다.

배열에 true를 할당하는 이유는 boolean[]의 초기값이 false이기 때문. Arrays.fill() 메소드를 활용하여 true로 초기화할 수도 있으나, 의미론적으론 좋지만 불필요한 연산이므로 false를 제곱ㄴㄴ수로, true를 제곱ㄴㄴ수가 아닌 수로 지칭한다. 배열 이름이 isNotPow인 이유도 이때문.

이후 isNotPow 배열을 순회하며, 값이 false인 수만 카운팅하면 된다.

[백준 / JAVA] 백준 알고리즘 1016번 제곱 ㄴㄴ수

백준 알고리즘

제곱 ㄴㄴ수

조건

문제

입력

출력

제한

케이스

예제 1

풀이

전체 소스

분류

🏷️ 태그

읽어주셔서 고마워요!