[Python 3] BOJ - 1016 "제곱 ㄴㄴ수"

 # 문제 링크 : https://www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

 

 # 풀이 :

개인적으로 이 문제의 핵심은 에라토스테네스의 체를 이용하는 것, 인덱스와 제곱 수의 관계를 이해하는 것이라고 생각한다. Min, Max의 값 자체는 매우 크지만, 실제 다뤄야할 배열의 크기는 최대 100만이므로 문제를 충분히 해결할 수 있다. 에라토스테네스는 1부터 n이하의 수에서 소수들을 구해주는 알고리즘이다. 그러나, 이 문제에서 에라토스테네스 알고리즘을 그대로 쓴다면 시간초과 및 메모리 초과가 날 것이기 때문에 약간의 변형이 필요하다

<그림 1. Min = 10, Max = 23>

 위의 그림 1은 Min이 10이고 Max가 23인 임의의 배열의 경우를 나타낸 것이다. square는 2이상 root(Max) 이하의 제곱수들로 이루어진 리스트이다. 비록 Max값이 문제의 최대 입력으로 주어진다 하더라고 root(Max)는 1억 미만이기 때문에 시간안에 square 배열을 구할 수 있다.

 이후 문제의 정의에 따라 제곱수의 배수인 수는 모두 없애줘야 한다. 에라토스테네스에서 소수의 배수를 지울 때 처럼 똑같은 방식으로 접근할 수 있다. 

<그림 2. 에라토스테네스 알고리즘 적용>

 위 그림 2에서 4의 배수 꼴은 빨간색으로, 9의 배수 꼴은 파란색으로, 16의 배수의 꼴은 초록색으로 지웠다. 그러나, 이것을 저장해야 할 배열이 필요한데, 아쉽게도 배열의 인덱스는 10부터 시작하는것이 아니라 0부터 시작한다. 그런데, 위 그림의 경우에서 인덱스 0에는 10을 저장하고, 인덱스 1에는 11을 저장하는 방식을 사용한다면, 인덱스 k일떄 실제 수는 10 + k가 될것이다. 즉, 정답을 저장하는 배열의 인덱스가 k라면 실제 값은 Min + k임을 알 수 있다.

 이제 모든 수에 대한 인덱스 처리는 완료되었다. 그러나 12,16,18,20과 같이 제곱수의 배수인 경우는 배열에서 제외시켜야 한다. 

<그림 3. 인덱스와 square의 규칙성>

 위 그림3의 배열에서 12,18,16은 각각 4,9,16의 배수 중 가장 작은 수이다. 우선 10을 각각 4,9,16으로 나눈 결과를 보면 각각 2.5, 1.111..., 0.625다. 여기서 나머지들은 버리고 몫만 취한 경우를 생각해보자. 각각 2,1,0이다. 다시 몫을 4,9,16으로 곱해주면 8,9,0이다. 8은 4를 더하면 4의 배수 중 가장 작은 수인 12가 되고, 9는 9를 더하면 9의 배수 중 가장 작은 수인 18이 되고, 0은 16을 더하면 16의 배수 중 가장 작은 수가 된다. 즉, Min을 각각의 제곱수로 나눈 후, 올림을 하게 되면 그 제곱수의 배수 중 가장 작은 수를 구할 수 있고 그 수에서 Min을 빼게 되면 각 제곱수의 배수가 시작하는 인덱스를 알 수 있게 된다.

 다시 말해, 12에서 10을 빼면 인덱스 2를 얻을 수 있고 18에서 10을 빼면 인덱스 8을 얻을 수 있고, 16에서 10을 빼면 인덱스 6을 얻을 수 있다.

<그림 4. 인덱스를 통한 점프>

  현재 어디서 각 제곱수의 배수가 시작되는 지 알았으므로, 해당 제곱수만큼 계속 더해주면서 범위 안에 있는 인덱스의 값을 모두 지워주면 된다. 위 그림4에서 보듯, 16은 12를 기준으로 4칸, 20은 16을 기준으로 다시 4칸을 더하여 갈 수 있다. 16의 경우, 배열의 최대값이 23이기 때문에 16에 16을 다시 더해줄 필요가 없으며 18의 경우도 마찬가지이다. 따라서 정답을 구할 수 있다.

 

 # 코드

import sys, math

# n = 최소, m = 최대
n, m = map(int, sys.stdin.readline().split())

# arr : 정답 배열
arr = [1 for _ in range(n,m+1)]

# square : 제곱수들
square = [v ** 2 for v in range(2, int(math.sqrt(m)) + 1)]

for i in square:
    # idx = 처음 시작되는 인덱스
    idx = (math.ceil(n / i) * i) - n
    # 범위를 만족하면 지워준다
    while idx <= m - n:
        arr[idx] = 0
        idx += i
ans = 0
for i in range(len(arr)):
    if arr[i] == 1:
        ans += 1
        
# 정답출력
print(ans)