[백준] 13909: 창문 닫기 - 파이썬[python]

풀이

• 문제에서 예시로 준 것을 사람 기준이 아닌 창문 기준으로 바꾸어 보자.
  그러면 1번째 창문은 1번째 사람만, 2번째 창문은 1&2째 사람, 3번째 창문은 1&3, 4번째 창문은 1&2&4째 사람이 열고 닫는다는 것을 알 수 있다.
• 즉, 각 창문은 약수의 개수만큼 열고 닫힌다. 그러므로 약수의 개수가 홀수이면 열려 있고 짝수이면 닫혀 있다.
• 따라서 우리는 열려 있는 창문의 개수를 구해야 하므로 약수의 개수가 홀수인 애들 즉, 제곱수만 카운팅하면 된다.

시간 초과

import sys,math

N = int(sys.stdin.readline())
cnt = 1 # 1의 약수의 개수는 홀수

for i in range(2, N+1):
    if int(math.sqrt(i))**2 == i: # 약수의 개수가 홀수 = 제곱수
        cnt += 1

print(cnt)

• int(math.sqrt(i))**2 == i 대신, math.sqrt(i).is_interger()를 쓸 수도 있다.
• 물론 여기서 이게 중요한 게 아니다.
• N은 21억까지 가능하다. 당연히 2부터 모든 21억까지 검사하면 시간 초과가 날 수도 있다는 생각을 했어야 했다...

풀이

• 배수든 소수든 곰곰이 생각해 보았다.
• 처음에는 제곱수인 것들을 set에 넣어두려고 생각했다.
• 그래서 1부터 21억의 1/2제곱까지 for문을 돌고 걔를 제곱해서 set에 넣는 코드를 짜다 보니..
• 21억의 1/2제곱까지가 범위라고? 어라 그러면 입력받은 수보다 작은 제곱수들의 개수만 구하면 끝이잖아?
• 따라서 sqrt든 **1/2든 이용해서 정수로 변환해주면 끝이겠다.
• 그게 바로 다음 코드이다.

코드

import sys,math

N = int(sys.stdin.readline())

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

• 꽤 고민한 결과인데 매우매우 짧다 ㅎㅎ..

결과

• 내 힘으로 푼 문제이다 히 뿌듯. 역시 백준은 재밌어 ㅎㅎ