[백준] 1016번 : 제곱 ㄴㄴ수

https://www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

해당 문제는 모든 경우의 수를 set 자료구조로 만들어서 전체에서 빼는 로직을 세웠으나, 메모리 복잡도에서 에러 판정을 받았다.

문제를 오랫동안 생각해보았지만 생각나지 않아서 정답을 찾아 보았다. 에라토스테네스의 체의 성질을 이용하여 문제를 해결하였다. visited 리스트를 0혹은1 상태로 저장하여 메모리 최적화를 하였습니다. min = 1, max = 1000 일때, 예를들어 visited[1000] 이면 1000은 제곱수를 나눌 수 있는수있지 없는 수인지 판별 하는 값습니다.

visited를 1로 초기화 한뒤, 제곱수로 나눌 수 있는 수를 모두 0으로 바꾸어준뒤, 1의 개수를 count하면 정답을 얻을 수 있습니다.

min, max 범위에서의 제곱수으로 나눌 수 있는 수를 찾아야하기때문에 min보다 크거나 같은 제곱수로 나눌수 있는 수를 찾습니다.

그리고 해당 수를 찾았다면 그와 관련된 배수들은 모두 나눌 수 있는 수 이기때문에(에라토스테네스의 체 성질) 모두 초기화 시켜줍니다.

 

다음과 같은 로직으로 문제를 해결 하면 된다.

 

1) i를 증가시켜보면서 최소값을 찾는다. ( i는 2*2, 3*3 에서 올 수 있는 수)

2) i로 나눌수 있을때 i로 나눌 수 있는 모든 배수의 수를 나눌 수 있는 수로 체크해준다.

min, max = map(int, input().split())
visited = [1] * (max - min + 1) # 최대 1,000,000

i = 2
while i*i <= max:
    temp = min//(i*i) # i*i 으로 나눌수 있는 최소값을 찾는다.
    if min%(i*i) != 0: # 만약 소숫점이 생긴다면 1을 추가해준다.
        temp += 1

    while temp *i*i <= max: # 에라토스테네스의 체 처럼 나누어지는수를 초기화 해준다.
        print(temp * i*i - min, i, temp)
        if visited[temp * i*i - min]:
            visited[temp * i*i - min] = 0
                
        temp += 1
    i += 1

print(visited.count(1))