[백준]_1016번 : 제곱 ㄴㄴ 수(파이썬)

1016번: 제곱 ㄴㄴ 수

문제의 전체 맥락을 보아하니 특정 자연수 구간에서 제곱 수로 나누어 떨어지는 수들을 제외시켜야 하는 작업이 필요하다. 제곱수들의 배수에 해당하는 숫자들을 지우면 되기 때문에 에라토스테네스의 체 알고리즘과 비슷한 맥락임을 알 수 있다.

 

즉 아래와 같은 코드로 시작하면 좋지 않을까 생각이 든다.

s, f = map(int, input().split())
# (int)(f ** 0.5)보다 큰 자연수의 제곱은 f보다 크기 때문에 관찰할 필요가 없다.
square = [i * i for i in range(2, (int)(f ** 0.5) + 1)] 
ans = [1] * (f + 1)

 

하지만 문제가 하나 있다. f의 값이 최대 1,000,001,000,000까지 커질 수 있다는 것이다. 파이썬의 리스트는 이렇게 큰 자료구조를 담을 여력이 없다. 즉 우리는 s와 f의 차이만큼으로 리스트를 압축해야 한다. 이 문제가 까다로워지는 것은 바로 이 부분 때문이다... 즉 ans 리스트를 아래와 같이 고쳐야 한다.

ans = [1] * (f - s + 1)

 

숫자 압축

위에서 s와 f를 각각 s를 차감함으로서 압축했으니까 square에 들어 있는 수들도 그렇게 압축하면 되지 않을까?

import sys

input = sys.stdin.readline
s, f = map(int, input().split())
square = [i*i for i in range(2, (int)(f**0.5)+1)] 
ans = [1]*(f - s + 1)
for piv in square:
    n = piv-s
    while n<=f-s:
        if n >= 0:
            ans[n] = 0
        n+=piv
print(sum(ans))

 

하지만 위의 코드는 심각한 허점 하나가 있다. s가 1,000,000,000,000이고(f는 방해되니까 잠시 접어두자) piv가 4일 때 어떤 상황이 일어나는지 살펴보자. n은 초기에 -999,999,999,996으로 초기화될 것이다. 문제는 n이 0 이상이 되기까지 while문에서 249,999,999,999번의 비교(n >= 0)와 덧셈(n+=piv)가 각각 일어난다는 것이다. 

 

결국 우리가 원하는 것은 s보다 작거나 같은 수들 중에서 최댓값을 찾는 것이다. 예를 들어 위의 경우에서는 piv가 4일 때는 누가 봐도 n은 1,000,000,000,000임이 자명하다. 반면에 piv가 9이면 1,000,000,000,008이 n이 된다. 이를 수식으로 풀어쓰면 아래와 같다. 

 

$n=piv\times\bigstar\leq s$

부등호의 등호를 만족 시키려면 $\bigstar=\frac{s}{piv}$

하지만 $n$이 자연수이기 위해서는 $\bigstar$은 반드시 자연수여야 하기 때문에 $\bigstar=s // piv$(몫)으로 나타낼 수 있다.

즉 $n=(s//piv)\times piv$

 

하지만 작은 문제 하나가 더 있다. 위의 마지막 공식을 이용해서 구한 n은 반드시 s보다 작거나 같다. 같을 때는 ans[n - s]에서 문제가 되지 않지만 작을 때는 미리 n에 piv를 더해주어야 한다.

최종 코드 >>

import sys

input = sys.stdin.readline
s, f = map(int, input().split())
square = [i * i for i in range(2, (int)(f ** 0.5) + 1)]
ans = [1] * (f - s + 1)
for piv in square:
    n = (s // piv) * piv
    if n - s < 0: n += piv
    while n <= f:
        ans[n - s] = 0
        n += piv
print(sum(ans))