[백준 문제풀이] 13909 - 창문 닫기

백준 문제풀이 13909번

풀이

이런 순서대로 창문이 열고 닫힌다.

1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)

범위는 $1<=N<=21억$ 이다.

순서대로 처리한다고 했을 때 21억이란 범위와 64mb의 메모리 제한, 1초라는 시간 제한때문에 문제가 틀릴게 뻔해서 다른 수를 찾아보았다.

일단 작은 범위의 수들부터 테스트하여 연관성이나 규칙을 찾아보려고하였다.

import sys

input = sys.stdin.readline

for N in range(테스트 할 범위):
    arr = [0] * N

    for i in range(N):
        for j in range(i + 1, N, i + 1):
            arr[j - 1] = 1 if arr[j - 1] == 0 else 0
    print(f"{N} : {sum(arr)}")

작은 수들을 테스트할 수 있는 코드를 만들었다.

1. 10까지

0 : 0
1 : 0
2 : 1
3 : 1
4 : 1
5 : 2
6 : 2
7 : 2
8 : 2
9 : 2
10 : 3

00 111 22222 3 .. 뒤에 이어지는 수도 연속될거라 생각하여 26까지 테스트해보았다

1. 26까지

0 : 0
1 : 0
2 : 1
3 : 1
4 : 1
5 : 2
6 : 2
7 : 2
8 : 2
9 : 2
10 : 3
11 : 3
12 : 3
13 : 3
14 : 3
15 : 3
16 : 3
17 : 4
18 : 4
19 : 4
20 : 4
21 : 4
22 : 4
23 : 4
24 : 4
25 : 4
26 : 5

잘 보면, 1, 4, 9, 16, 25에서 열린 창문의 개수가 달라지는 걸 알 수 있다. 그리고 이 수들은 순서대로 수의 제곱과 같다. $1, 2^2, 3^2, 4^2, 5^2$

그러므로 각 열린 창문의 개수는 수들의 제곱근에 int를 씌워준 것과 같다는 결론이 나온다. 즉

int(n**0.5) 가 정답이 될 수 있다는 결론이 나온다.

그리고 실제로 수를 넣어 테스트해보면 정답이라는걸 알 수 있다.

코드

# import sys

# input = sys.stdin.readline

# for N in range(27):
#     arr = [0] * N

#     for i in range(N):
#         for j in range(i + 1, N, i + 1):
#             arr[j - 1] = 1 if arr[j - 1] == 0 else 0
#     print(f"{N} : {sum(arr)}")

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