[PS] BOJ 13909 / 창문 닫기

Minjun Kim

06 Oct 2025 • 3 min read

Thumbnail: Photo by Kevin Martin Jose (Unsplash)

문제 링크: https://www.acmicpc.net/problem/10986

작은 수에 대해서 직접 풀어보면 규칙이 보입니다.

풀이

규칙 찾기

$N$개의 창문이 있을 때, $i$번째 사람은 $i$의 배수에 해당하는 창문의 상태를 뒤집습니다 (창문이 열려 있다면 닫고, 닫혀 있다면 엽니다.)
모든 창문은 처음에 닫혀 있습니다.

단순히 위 조건만 봐서는 감이 오질 않으니, 적당히 작은 $N$에 대해서 창문이 열리고 닫히는 과정을 직접 따라해보며 이해해봅시다.

$N = 1 \cdots 16$에 대해, 창문이 열리고 닫히는 과정을 추적하는 코드를 작성했습니다. 직접 과정을 보고 싶으시다면, 아래 코드를 실행해 출력 결과를 확인해보시면 됩니다.

input = open(0).readline

windows = [False] * 17 # 1 ~ 16의 창문 상태를 저장. True일때 열린 것이다.
trace = [[] for _ in range(17)] # 각 창문을 누가 건드렸는지 기록한다.

def simulate(n):
    """1 ~ n까지 창문을 열고 닫는 과정을 추적한다."""
    # init
    for i in range(len(windows)):
        windows[i] = False
        trace[i].clear()
    # simulate
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            windows[j] = not windows[j]
            trace[j].append(i)
    # result
    print("[Windows]")
    cnt = 0
    for i in range(1, n + 1):
        print(f"{i}: {'OPEN' if windows[i] else 'CLOSED'}")
        if windows[i]:
            cnt += 1

    print("\n[Trace]")
    for i in range(1, n + 1):
        print(f"{i}: {' '.join(map(str, trace[i]))}")
    print(f"\n[OPEN]\n{cnt}")

for i in range(1, 17):
    print("-"*6)
    print(f"N = {i}\n")
    simulate(i)
    print()

시뮬레이션 코드

N = 1~3

1번 창문만 열려 있게 됩니다.

N = 4 ~ 8

1번 창문과 4번 창문만 열려 있습니다.

N = 9~15

1, 4, 9번 창문만 열려 있습니다.

N = 16

1, 4, 9, 16번 창문만 열려 있습니다.

고찰

앞선 예시를 통해, $N$번 사람까지 창문을 건드린 뒤에 열려 있는 창문들은 모두 제곱수입니다.

처음 창문이 닫혀 있기 때문에, 해당 창문을 "홀수 번" 건드려야 마지막에도 창문이 열려 있게 됩니다. 이 때, $i$번 창문을 건드리는 사람들은 모두 $i$의 약수입니다. 따라서, $i$번 창문의 약수의 개수에 따라 창문이 열려 있을지, 닫혀 있을지가 결정됩니다.

모든 제곱수가 아닌 자연수는 짝수 개의 약수를 가지고, 오로지 제곱수만 홀수 개의 약수를 가집니다. 따라서, 마지막에 열려 있는 창문은 모두 제곱수에 해당합니다.

즉, 이 문제는 $N$이하의 제곱수의 개수를 찾는 문제로 생각할 수 있습니다.

전체 코드

input = open(0).readline

N = int(input())
cnt = 0
i = 1
while i * i <= N:
    i += 1
    cnt += 1
print(cnt)

solution.py

풀이

​규칙 찾기