[Baekjoon] 13909 - 창문 닫기 (Python)

문제

[BaekJoon] 13909 창문 닫기

1차 시도 (메모리 초과)

단순히 창문을 배열로 선언해놓고 2중 for문을 돌면서 열려 있으면 닫고, 닫혀 있으면 열도록 구현해보았다.

하지만

입력 조건 : 1 <= N <= 2,100,000,000

N이 21억이라면 아래 내가 쓴 코드 처럼 반복으로 풀면 결과는 같을지언정 문제를 해결할 수는 없다. (메모리 초과)

import sys
input = sys.stdin.readline

n = int(input())
windows = [0] * (n+1)

for i in range(1, n+1): 
    for j in range(i, n+1, i):
        if windows[j] == 0:
            windows[j] = 1
        elif windows[j] == 1:
            windows[j] = 0
            
print(sum(windows))

2차 시도 ✅

약간의 구글링으로 이해를 도왔다,,

창문 번호인 n이 약수의 개수와 관련이 있다는 것이다.

n이 6일 때, n의 약수는 1, 2, 3, 6으로 4개의 약수가 있으므로 열고 닫히는 창문의 상태가 4번 바뀌게 된다는 것이다.

첫번째 사람은 모든 창문을 열고,

두번째 사람은 2, 4, 6, 8, 10.. 번 창문을 닫는다.

약수의 갯수가 홀수개라면 창문을 홀수번 열고 닫은 것이므로 마지막엔 열려있다.

약수의 갯수가 짝수개라면 창문을 짝수번 열고 닫은 것이므로 마지막엔 닫혀있다.

n	열린 창문의 개수
1	1
2	1
3	1
4	1
5	2
6	2
..	..
9	2
10	3
..	..
16	3
17	4

제곱수의 다음 번호부터 1씩 증가한다.

그래서 Input인 n까지 중 가장 큰 n의 제곱근을 출력하면 된다,,

import sys
input = sys.stdin.readline

n = int(input())
print(int(n**0.5))

이게 뭐야