[python] 백준 4811 알약

4811번: 알약 (acmicpc.net)

4811번: 알약

 
 

문제

첫째 날에 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.
다음 날부터 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.
 
한 조각을 꺼낸 날에는 W, 반 조각을 꺼낸 날에는 H
총 2N일이 지나났을 경우, 가능한 서로 다른 문자열의 개수는??
 

풀이

2차원 dp를 이용해서 풀어야 하는 문제
dp[i][j] : 알약 반 개를 i개 먹고, 알약 한 개를 j개 먹었을 때의 경우의 수
 

점화식 : dp[i][j] = dp[i-1][j] + dp[i][j-1] 

(알약 반 개 i-1개, 알약 한 개 j개) 먹은 경우에서  알약 반 개를 먹음
+ (알약 반 개 i개, 알약 반 개 j-1개) 먹은 경우에서 알약 한 개를 먹음
 

dp = [[0]*31 for _ in range(31)]    #0개 먹었을 때부터 30개 먹었을 때까지
                                    #행은 반 개 먹은 개수, 열은 한 개 먹은 개수

for i in range(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] #(반개를 i-1개, 한 개를 j개) + (반개를 i개, 한 개를 j-1개)

while True:
    N = int(input())
    if N ==0: #입력으로 0이 들어오면 함수 종료
        break
    print(dp[N][N])