[백준1016번] 제곱 ㄴㄴ수 / Python3

문제

어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 [min,max]구간에 제곱ㄴㄴ수가 몇 개인지 출력한다.

예제 입력 1

1 10

예제 출력 1

7

나의 풀이

이 문제는 에라토스테네스의 채를 응용하는 문제였다. 처음에는 에라토스테네스의 채는 소수를 걸러내는데에만 사용하는 줄알고 소수를 걸러내어 소수로 min부터 max까지 소수의 제곱수들로 나누어 떨어지는 수들의 개수를 골라내었지만 역시나 시간초과가 발생하였다. 알고보니 이 문제는 최대 범위가 1,000,000으로 채로 사용할 list의 최대 크기가 될 수 있었고, 주어지는 min과 max를 0 ~ 1,000,000범위 안으로 바꾸어서 2부터의 제곱 수의 배수들을 채로 걸러내는 방식의 문제였다.

따라서 이 문제의 핵심으로는 주어지는 minmax에서 `01,000,000의 범위로 표현해내는 방법이었다. 처음에 어렵다고 생각을 했지만 이해를 하고나니까 쉬웠던 것 같다. min과 max사이에서 처음으로 i의 제곱으로 나누어 떨어지는 수를 구해야한다. 그럼 간단히 min을 i의 제곱으로 나누어 주면 된다. 주의할 점은 나누어 떨어지지 않는 경우에는 1을 더해주는 것이다. 예를들자면 min과 max가 각각 50~100으로 주어졌다고 생각해보자. 그럼 i가 2일때 제곱인 4로 min값인 50을 나누면50 // 4 = 12`이다. 그럼 12에 4를 다시 곱하면 48이 된다. 이러면 처음에 주어진 50과 100사이의 값이 아니므로 잘 못된결과가 나온다. 따라서 1을 더해 13이라면 52가 되어 정상적인 범위로 들어온다. 만약 52~100사이의 값이라 min값이 4로 나누어떨어진다면 어떨까? 그렇다면 그대로 사용하면 된다.

위처럼 범위 안의 배수를 곱하기 시작할 수 있는 수를 구하고 나면 이제 에라토스테네스의 채를 사용하여 최대 범위까지 i제곱의 배수에 해당하는 곳에 모두 방문 처리를 해주면서 count를 하나씩 감소시키면서 2부터 최대 범위까지의 i값을 탐색하면 남은 제곱 ㄴㄴ수의 개수가 count에 저장이 되게된다.

이 문제가 해답을 봐도 금방 이해가 가지않아 애를 먹었다... 하지만 천천히 따져가며 생각을 해보니 이해가 되었다. 중간에 설명한 처음으로 시작되는 배수 s를 구하는 것이 정말 관건이었던 것 같다.

코드

# 1016번 제곱 ㄴㄴ수

# main
minNum, maxNum = map(int,input().split())

eratos = [False for _ in range(maxNum-minNum+2)]

cnt = maxNum - minNum + 1
i = 2
while i**2 <= maxNum:
    s = minNum // (i**2)
    if minNum % (i**2) != 0:
        s += 1

    while s*(i**2) <= maxNum:
        if not eratos[s*(i**2) - minNum]:
            eratos[s*(i**2) - minNum] = True
            cnt -= 1
        s += 1
    i += 1

print(cnt)