[Python/파이썬] 백준 4811번 알약

 

4811번: 알약

 

문제

70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.

첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.

다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.

종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

입력

입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서 가능한 문자열의 개수를 출력한다.

코드

while True:
    n = int(input())
    if n == 0:
        break
    dp = [[0]*(n+1) for _ in range(n+1)]  # 행: W, 열: H
    dp[0][0] = 1
    for i in range(1, n+1):
        dp[i][0] = dp[i-1][0]
        for j in range(1, n+1):
            if j > i:
                continue
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    print(dp[n][n])

dp 배열의 행은 W의 개수, 열은 H의 개수이다. 알약이 온전한 한 조각이 쪼개져야만 반 조각이 되므로 이미 만들어진 문자열에는 H의 개수가 W의 개수보다 작거나 같아야만 한다. 그러므로 반복문을 돌 때 열의 인덱스(j)가 행의 인덱스(i)보다 큰 경우는 continue해주어야 한다. 그렇지 않다면 점화식은 다음과 같다.

$$dp[i][j] = dp[i-1][j]+dp[i][j-1]$$

W를 하나 추가하는 경우(dp[i-1][j])와 H를 하나 추가하는 경우(dp[i][j-1])를 더하면 된다.