Python으로 푸는 백준 6359. 만취한 상범

백준 6359. 만취한 상범

기숙사 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 

각 방에는 벌점을 많이 받은 학생들이 구금되어 있다.

감옥 간수인 상범이가 문을 열고 닫는 게임을 했을 때,

모든 게임이 끝나고 난 후에 열린 문으로 도망친 학생의 수를 구하는 프로그램을 짜시오.

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

Github에서 코드 보기

문제 조건

감옥에 주어진 N개의 방을 열고 닫는 게임을 한다.

1부터 n의 숫자가 될때까지 숫자들을 k(1<=k <=n)라고 한다.

k의 간격 만큼 떨어진 감옥의 방문이 열려 있으면 열고, 닫혀 있으면 닫는다.

문제 풀이

방문이 열려 있는지 닫혀있는지 기록된 dom이라는 리스트가 존재한다.  1부터 시작하는 k가 n이 될때까지 재귀가 돈다. 함수에서는 주어진 k의 간격만큼 떨어진 방문들을 열고 닫는다. 사실 이 문제는 재귀로 풀지 않고 2중 for문으로 푸는게 더 적합할 것 같으나 알고리즘의 분류가 DP로 되어 있으므로 그 방식대로 문제를 해결하였다. 

파이썬 코드

import sys
input = sys.stdin.readline
 
 
def solve(dom, k, n):
 
    if k == n + 1:
        print(dom.count(1))
        return
    
    # k간격만큼 문 열고 닫기
    for i in range(k-1, n, k):
        if dom[i] == 0: dom[i] = 1
        elif dom[i] == 1: dom[i] = 0
    solve(dom, k+1, n)
 
 
if __name__ == '__main__':
    n = int(input().strip())
    for i in range(n):
        count = int(input().strip()) # 감옥의 총 수
        dom = [0]*count # 감옥
        solve(dom, 1, count)