(Python/🥇5)백준알고리즘 4811번: 알약

문제 바로가기 

알약

 

문제:

70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다. 첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다. 다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다. 종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

입력:

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

출력:

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

 

풀이:

 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')


dp = [[0] * 31 for _ in range(31)] 
for i in range(1, 31):
    dp[0][i] = 1 # 매일 1개 짜리 먹는 경우
for i in range(1,31):
    for j in range(i,31):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
while True:
    N = int(input())
    if N == 0 :
        break
    print(dp[N][N])

 

dp는 w갯수와 h갯수인 2차원 배열로 선언한다. 

그럼 dp[w][j] 는알약 반 개를 i개 먹고, 알약 한 개를 j개 먹었을 때의 경우의 수

 

그리고 dp[0][i] 는 1개 로 고정이다.

 

그리고 점화식을 세우면 

(알약 반 개 i-1개, 알약 한 개 j개) + (알약 반 개 i개, 알약 한 개 j-1개) 이다