[백준6359번] 만취한 상범 / Python3

문제

서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다.

그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있다면 연다. k번째 라운드에서는 번호가 k의 배수인 방이 열려 있으면 잠그고, 잠겨 있다면 연다. 이렇게 n번째 라운드까지 진행한 이후, 상범이는 위스키의 마지막 병을 마시고 쓰러져 잠든다.

구금되어있는 몇 명(어쩌면 0명)의 학생들은 자신의 방을 잠그지 않은 채 상범이가 쓰러져버렸단 것을 깨닫고 즉시 도망친다.

방의 개수가 주어졌을 때, 몇 명의 학생들이 도주할 수 있는지 알아보자.

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄에 한 개씩 방의 개수 n(5 ≤ n ≤ 100)이 주어진다.

출력

한 줄에 한 개씩 각 테스트 케이스의 답, 즉 몇 명이 탈출할 수 있는지를 출력한다.

예제 입력 1

2
5
100

예제 출력 1

2
10

나의 풀이

문의 열리고 닫힌 상태의 여부를 저장하는 배열을 만들고, k를 1부터 n까지 for문을 돌면서 k의 배수에 해당되는 모든 원소에 대하여 상태를 바꿔주고 마지막에 상태를 저장하는 배열에서 열린상태의 개수를 세어 출력해주면 된다. 시간이나 메모리에 대한 제약이 크지 않아 그렇게 어려운 문제는 아니었던 것 같다. 다이나믹 프로그래밍 카테고리에 있는 문제라 메모제이션을 사용해야하나?라는 생각을 해보면서 조금 시간이 걸렸던 문제였다.

코드

# 6359번 만취한 상범
import sys

# main
t = int(sys.stdin.readline())

for _ in range(t):
    n = int(sys.stdin.readline())

    # 0 : 닫힘, 1 : 열림
    dp = [0 for _ in range(n+1)]
    for k in range(1,n+1):
        tmp = k
        i = 2

        while tmp <= n:
            if dp[tmp] == 0:
                dp[tmp] = 1
            else:
                dp[tmp] = 0

            tmp = k * i
            i += 1

    print(dp.count(1))