백준 15736 청기백기 파이썬 문제풀이 (python 정수론 최적화)

문제 보러가기

 

백준 청기백기 파이썬 문제풀이

N개의 깃발을 1의 배수를 뒤집고, 2의 배수를 뒤집고 차례로 N의 배수까지 뒤집는다. 

깃발은 처음에는 다 청색인데 뒤집으면 백색이다.

마지막까지 진행하면 백색으로 보이는 깃발이 몇갠지 알아내는 문제이다.

 

뭔가 에라토스테네스의 체가 생각나는 문제이다.

N의 범위는 21억까지인데, 시간상 이걸 하나씩 처리할리가 없다. 

 

어떤 규칙이 있을까.

약수의 관점

하나씩 손으로 써내려가다보니 i번째 깃발은 i의 배수 차례를 지나가면 더 이상 바뀌지 않는다.

즉 1~i까지 바뀌고, 약수번째일 때 바뀐다.

 

정리하면 약수의 개수반큼 뒤집히고, 처음은 모두 청색이니까 홀수번 바뀌어야한다.

즉 약수의 개수가 홀수개여야한다.

 

그렇다고 숫자 하나하나씩 약수가 몇 개인지 셀 수 없다.

 

약수가 홀수인 수의 특징

고민을 하다가 보니 약수가 홀수개여야하는 조건을 떠올리게 되었다.

 

약수가 3개라면, 9를 예로 들어보자.

약수는1 3 9이다.

1과 자기 자신 이외에 하나가 있고, 그 하나를 제곱한 수가 된다.

 

약수가 5개라면, 1과 자기 자신 이외에 3개의 약수가 있다.

16이 약수가 5개인 수 인데, 약수는 1 2 4 8 16 이다.

1,16을 빼면 2 4 8 중 2와 8을 곱하면 16이다.

나머지 4는 스스로 제곱해야 16이 되는데.

 

여기까지 보았을 때 약수가 홀수인 수의 특징이 보이는가?

바로 어떤 수의 제곱수라는 점이다.

 

즉 범위 안의 제곱수를 찾으면 된다는 가설이 세워진다.

 

몇 개인지 구하기

몇 개인지 구하는 방법은 일일히 세는 방법은 절대 시간이 안된다.

 

제곱 수라는 것을 알았고, N까지 진행한다면

1부터 제곱한 수를 하나씩 찾아서 제곱수가 N보다 커지는 시점을 찾으면 된다.

 

구현해보자.

N = int(input())
answer = 0

for i in range(1, N+1):
    square = i*i
    if square > N:
        answer = i - 1
        break

print(answer)

 

잉? 95% 까지 갔다가 틀렸다.

 

아.. 1을 넣은 경우를 착각했다.

위 코드의 경우 n=1이면 반복문이 정상작동하지 못하고 0이 도출된다.

1번째는 무조건 백기가 나오는데 말이다.

 

문제는 1인 경우에 1하나의 케이스만 확인하고 반복문이 끝났다는 것이다.

while 문으로 하는 것이 더 옳은 방법이었다.

N = int(input())

i = 1
square = i*i
while square <= N:
    i += 1
    square = i * i

print(i-1)

 

 

다른 방법으로는 

import math

N = int(input())

print(int(math.sqrt(N)))