[ 백준 ] 1557 제곱ㄴㄴ ( Python )
K번째 제곱ㄴㄴ수 찾기
안녕하세요! 오늘은 주어진 K에 대해 K번째 제곱ㄴㄴ수를 찾는 문제를 함께 풀어보도록 하겠습니다. 제곱ㄴㄴ수란 1이 아닌 제곱수로 나누어지지 않는 수를 말합니다. 예를 들어, 1, 2, 3, 5, 6, 7, 10, 11, 13 등이 제곱ㄴㄴ수에 해당합니다.
접근 방법
이 문제를 풀기 위해서는 제곱ㄴㄴ수의 개수를 효율적으로 세는 방법을 고안해야 합니다. 단순히 모든 수를 일일이 확인하는 것은 시간 복잡도 측면에서 비효율적일 것입니다.
여기서는 포함-배제의 원리(Inclusion-Exclusion Principle)를 활용하여 제곱ㄴㄴ수의 개수를 계산하는 방법을 사용하겠습니다. 이 원리는 여러 개의 집합에 대한 합집합의 크기를 구할 때 유용하게 사용됩니다.
또한, 제곱수를 구성하는 소수(prime)들의 목록을 미리 생성해 두는 것이 계산 속도를 향상시키는 데 도움이 될 것입니다.
왜 이렇게 생각하고 이렇게 풀었는가?
이 문제를 접근할 때, 가장 먼저 떠오른 생각은 단순히 모든 수를 하나씩 확인하면서 제곱ㄴㄴ수인지 판단하는 것이었습니다. 하지만 이 방법은 시간 복잡도가 $O(N)$으로 매우 비효율적입니다. 문제의 제한 사항에서 K의 범위가 $1 \leq K \leq 1,000,000,000$ 으로 주어졌기 때문에, 단순한 방법으로는 시간 초과가 발생할 것입니다.
그래서 더 효율적인 방법을 고민하던 중, 포함-배제 원리를 활용하면 제곱ㄴㄴ수의 개수를 빠르게 계산할 수 있다는 아이디어가 떠올랐습니다. 제곱수들의 합집합을 구하고, 이를 전체 수에서 빼면 제곱ㄴㄴ수의 개수를 구할 수 있습니다.
포함-배제 원리는 다음과 같은 수식으로 표현할 수 있습니다.
\[\begin{aligned} |A_1 \cup A_2 \cup \cdots \cup A_n| = & \sum_{i=1}^{n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| \\ & + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots \\ & + (-1)^{n-1} |A_1 \cap A_2 \cap \cdots \cap A_n| \end{aligned}\]여기서 $A_i$는 $i$번째 소수의 제곱수들의 집합을 나타냅니다.
하지만 모든 제곱수를 고려하는 것도 비효율적이라는 생각이 들었습니다. 그래서 제곱수를 구성하는 소수들의 목록을 미리 생성해 두고, 이를 활용하여 계산하는 방법을 선택했습니다. 에라토스테네스의 체를 사용하여 소수를 빠르게 구할 수 있습니다.
에라토스테네스의 체는 다음과 같은 단계로 이루어집니다.
- 2부터 $\sqrt{n}$까지의 모든 수를 나열합니다.
- 아직 지워지지 않은 수 중에서 가장 작은 수를 찾습니다. 이 수를 $p$라고 하고, 이 수는 소수입니다.
- $p$를 제외한 $p$의 배수를 모두 지웁니다.
- 아직 모든 수를 처리하지 않았다면, 다시 2번 단계로 돌아가 반복합니다.
마지막으로, K번째 제곱ㄴㄴ수를 찾기 위해 이진 탐색을 활용했습니다. 탐색 범위를 줄여가면서 효율적으로 정답을 찾을 수 있습니다.
이렇게 포함-배제 원리, 소수 목록 생성, 이진 탐색을 조합하여 문제를 해결할 수 있었습니다. 각각의 아이디어가 시간 복잡도를 크게 개선시켜주었고, 제한 시간 내에 정답을 구할 수 있게 해주었습니다.
풀이 과정
먼저
generate_primes함수를 사용하여 문제에서 필요한 범위 내의 소수들을 생성합니다. 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용하여 소수를 효율적으로 찾아냅니다.이진 탐색(Binary Search)을 사용하여 K번째 제곱ㄴㄴ수를 찾습니다. 탐색 범위의 시작을 1로, 끝을 $2^{31}$로 설정합니다.
check함수를 사용하여 주어진 수num까지의 제곱ㄴㄴ수의 개수를 계산합니다. 이 함수에서는 포함-배제의 원리를 적용하여 계산을 수행합니다.- 소수의 제곱들로 구성된 집합들의 합집합의 크기를 구합니다.
- 각 집합의 크기는
num을 해당 소수의 제곱으로 나눈 몫과 같습니다. - 포함-배제 원리에 따라 홀수 개의 집합이 포함된 경우 더하고, 짝수 개의 집합이 포함된 경우 뺍니다.
- 최종적으로
num에서 합집합의 크기를 빼면 제곱ㄴㄴ수의 개수를 얻을 수 있습니다.
이진 탐색을 진행하면서
check함수를 사용하여 현재 탐색 범위의 중간값까지의 제곱ㄴㄴ수의 개수를 계산합니다.- 개수가 K보다 작으면 탐색 범위의 시작을 중간값 + 1로 늘립니다.
- 개수가 K보다 크거나, 개수는 K와 같지만 중간값 자체가 제곱수인 경우 탐색 범위의 끝을 중간값 - 1로 줄입니다.
- 개수가 K와 같고 중간값이 제곱ㄴㄴ수인 경우 탐색을 종료합니다.
최종적으로 찾은 값을 출력합니다.
이 풀이에서 가장 중요한 부분은 포함-배제 원리를 활용하여 제곱ㄴㄴ수의 개수를 효율적으로 계산하는 것입니다. 이를 위해 소수 목록을 미리 생성하고, 각 소수의 제곱들로 구성된 집합들의 합집합의 크기를 구합니다. 이 과정에서 스택을 사용하여 DFS 방식으로 탐색을 진행하며, 포함 여부에 따라 합집합의 크기에 더하거나 빼는 작업을 수행합니다.
또한, 이진 탐색을 활용하여 K번째 제곱ㄴㄴ수를 찾는 것도 중요한 부분입니다. 탐색 범위를 줄여가면서 효율적으로 정답을 찾을 수 있습니다.
이렇게 포함-배제 원리와 이진 탐색을 적절히 활용하여 문제를 해결할 수 있었습니다. 각각의 아이디어가 시간 복잡도를 크게 개선시켜주었고, 제한 시간 내에 정답을 구할 수 있게 해주었습니다.
이상으로 K번째 제곱ㄴㄴ수 찾기 문제에 대한 풀이를 마치겠습니다. 감사합니다!
해답 보기
전체코드
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
def check(num):
count = 0
has_square_free = 0
stack = [(1, -1, 1)]
while stack:
current, idx, sign = stack.pop()
for j in range(idx + 1, prime_count):
next_num = current * (primes[j] ** 2)
if next_num > num:
break
count += (num // next_num) * sign
has_square_free |= int(num % next_num == 0)
stack.append((next_num, j, -sign))
return num - count, has_square_free
def generate_primes(limit):
primes = []
is_prime = [True] * (limit + 1)
for i in range(2, limit + 1):
if is_prime[i]:
primes.append(i)
for multiple in range(i * i, limit + 1, i):
is_prime[multiple] = False
return primes
primes = generate_primes(50000)
prime_count = len(primes)
K = int(input())
x = 1 << 31
shift = 30
while True:
k, has_square_free = check(x)
if k < K:
x += 1 << shift
elif k > K or (k == K and has_square_free):
x -= 1 << shift
else:
break
shift -= 1
print(x)