본문 바로가기

카테고리 없음

[백준 1016번] 제곱 ㄴㄴ 수 (Python3)

import sys
input = sys.stdin.readline
from math import sqrt,ceil

sieve = [1]*1000002
sieve[0] = sieve[1] = 0
prime = []
for i in range(2,1000002):
  if sieve[i]==0:
    continue
  prime.append(i)
  if i>1000:
    continue
  n = 2
  while i*n<=1000001:
    sieve[i*n] = 0
    n += 1

min,max = map(int,input().split())
check = {i:1 for i in range(min,max+1)}

cnt = max-min+1
for p in prime:
  p = p**2
  n = ceil(min/p)
  while p*n<=max:
    if check[p*n]:
      check[p*n] = 0
      cnt -= 1
    n += 1

print(cnt)

 

간단한 문제인데 시간복잡도를 잘못 생각해서 뻘짓한 문제이다.

 

사실 풀이는 문제 보자마자 떠올랐는데, 압도적인 숫자범위 앞에서 (숫자크기 1조, 범위 100만) 당연히 이 풀이는 아닐거라고 생각하고 다른 방법 찾는다고 고민고민하다가 그냥 제출해봤더니 맞았다.

 

알고리즘을 요약하면 이러하다.

1. 숫자의 범위가 최대 1조이므로, 소수를 100만범위까지 구해준다. (100만의 제곱이 1조이므로)

2. 소수는 에라토스테네스의 체 방식으로 구하며, 이때 for문은 1000까지만 돌린다 (1000의 제곱이 100만이므로)

3. 각 소수의 제곱수에 대해서 에라토스테네스의 체 방식으로 min부터 max까지 제곱수의 배수를 걸러준다.

 

 

시간복잡도에 대해서 아직 익숙지 않은 부분이 많다는걸 알려주는 문제였다.

 

오늘의 교훈) 시간복잡도에 대해서 더 정확하게 판단하자