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

백준 플레 도전기 - 1

2021년 10월 11일

한참 남음!

백준 1016번

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

이 문제를 읽고 가장 먼저 들었던 생각이 에라토스테네스의 체이다.
에라토스테네스의 체는 소수를 찾는 알고리즘으로 <위키피디아>의 설명을 보면 다음과 같다.

먼저
2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
자기 자신을 제외한 2의 배수를 모두 지운다.
남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
자기 자신을 제외한 3의 배수를 모두 지운다.
남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
자기 자신을 제외한 5의 배수를 모두 지운다.
남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
자기 자신을 제외한 7의 배수를 모두 지운다.
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
그림의 경우, 11*11 > 120이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

풀이

소수를 위와 같은 방식으로 구할 수 있는데,

이 방법을 응용해서 이 문제, 제곱 ㄴㄴ 수에 적용하려고 한다.
범위 내의 수들 제곱수로 나뉘어 떨어지는지를, 즉 제곱수의 배수인지를 조사한 뒤 그 개수를 셀건데 이미 개수에 넣은 수가 또 나오면 중복이 되므로, 리스트를 만들어서 이미 카운트한 수는 True값을 할당해주는 방식으로 알고리즘을 짜려고 한다.

min, max = map(int, input().split())

answer = max - min + 1

먼저 최솟값과 최댓값을 받고 answer 값에 범위 내에 포함되는 수의 개수를 넣어준 뒤,
'제곱수의 배수'의 개수를 answer에서 빼줄거다.

divisibleByTheSquare = [False] * (max-min+1)
#범위가 만약 32부터 36이라고 하면 divisibleByTheSquare[0], divisibleByTheSquare[1]은
#각각 32와 33을 가리킨다.

#여기서 False는 제곱의 배수가 아닌 수라면
#아래 코드에서 True로 바뀌는 수는 제곱의 배수겠죠?

이렇게 찾고자 하는 범위만큼의 리스트를 만들고 False 값을 할당해준다.
그 후에 범위 내에서 제곱수의 배수를 찾게되면 그 수에 해당하는 인덱스를 divisibleByTheSquare에서 True값으로 바꿔주고 answer 값에서 1을 빼주면 된다.

for i in range(2, int(max**0.5+1)):

위의 에라토스테네스의 체에서처럼 나눌 수는 2의 제곱부터 int(max**0.5)의 제곱까지만 고려하면 된다.

for i in range(2, int(max**0.5+1)):
    square = i**2
    for j in range((((min-1)//square)+1)*square, max+1, square):

이제 제곱수인 4, 9, 16 같은 것들이 범위 내의 수를 나누어 떨어지게 하면 그 수에 해당하는 인덱스를 divisibleByTheSquare에서 True값으로 바꿔준다.

이때 범위를 ((((min-1)//square)+1)*square, max+1, square) 이렇게 해준 이유는,
min이상의 가장 작은 square의 배수부터 square만큼 커지는 수만 계산하기 위함이다.
이해하려고 노력해보셈!

for i in range(2, int(max**0.5+1)):
    square = i**2
    for j in range((((min-1)//square)+1)*square, max+1, square):
      if not divisibleByTheSquare[j-min] : 		#해당 인덱스 값이 False라면
                  divisibleByTheSquare[j-min] = True 	#True 바꿔준 뒤
                  answer -= 1 				#answer에서 1을 빼줌
 	#다음 반복에서는 나뉘어 떨어지더라도 이미 TRUE이기 때문에 answer에서 1이 빼지지 않음.

가장 밖의 for문을 다 돌게 되면 answer에서 제곱으로 나누어 떨어지는 수의 총 개수만큼 빼진다.

전체코드

min, max = map(int, input().split())

answer = max - min + 1
divisibleByTheSquare = [False] * (max-min+1)

for i in range(2, int(max**0.5+1)):
    square = i**2
    for j in range((((min-1)//square)+1)*square, max+1, square):
        if not divisibleByTheSquare[j-min] :
            divisibleByTheSquare[j-min] = True
            answer -= 1
print(answer)

골드1 치고는 쉬운 문제였던 듯

첫 포스팅 힘들다,,