본문 바로가기

카테고리 없음

[백준 1557번] 제곱 ㄴㄴ (Python3)

def check(x):
  cnt = 0; sq = 0
  q = [(1,-1,1)]
  while q:
    n,i,s = q.pop()
    for j in range(i+1,P):
      n1 = n*prime[j]**2
      if n1>x:
        break
      cnt += x//n1*s
      sq |= int(not x%n1)
      q.append((n1,j,-s))
  return x-cnt,sq

prime = []; visited = [0]*50001
for i in range(2,50001):
  if not visited[i]:
    prime.append(i)
    if i<317:
      for j in range(1,50000//i+1):
        visited[i*j] = 1
P = len(prime)
K = int(input())
x,c = 1<<31,30
while 1:
  k,sq = check(x)
  if k<K:
    x += 1<<c
  elif k>K or k==K and sq:
    x -= 1<<c
  else:
    break
  c -= 1
print(x)

이분탐색 + 에라토스테네스의 체로 해결하였다.

 

풀이를 설명하면,

1. 에라토스테네스의 체로 1~50000 사이의 소수를 구한다.

2. 1~x 사이에 제곱수가 몇개인지 구하는 check 함수를 만든다. 각 소수들의 곱의 제곱으로 이루어진 제곱수들의 배수의 개수의 합을 구해주면 되는데, 이때 포함-배제의 원리에 따라 곱해진 소수들의 개수가 홀수면 더해주고, 짝수면 빼주어야 한다. 또, x가 제곱수의 배수인지도 확인한다.

3. 이분탐색으로 1~x 사이의 제곱ㄴㄴ수의 개수(x-제곱수 배수의 개수)가 K개이고, x가 제곱ㄴㄴ수인 x값을 찾아 출력한다.

 

제곱 ㄴㄴ 수[백준 1016번] 제곱 ㄴㄴ 수 (Python3) (tistory.com) 를 이미 풀어본 경험이 있어 쉽게 해결했던 것 같다. 당시에 쉽게 풀이를 떠올려놓고도 시간복잡도상 안될 것이라 단정지어서 풀지 못했었다. 이번에도 사실 check 함수의 시간복잡도가 언뜻보면 O(N^3) (N은 소수의 개수) 로 보이는데, 사실 x보다 작은 숫자에 대해서만 판별하기 때문에 훨씬 적은 시간에 통과될 수 있다.

 

 

오늘의 교훈) 숫자의 제한에 따른 시간복잡도를 면밀이 검토해야한다.