백준 4811번(Python): 알약

---

[풀이]

 

  반 개 'H'인 경우는 그전에 한개를 쪼갠적이 있어야 한다. 이 말뜻을 다시 생각해보면 'H'의 개수가 'W'의 개수보다 많으면 안된다는 것이다.

 

DP[i][j] : 알약 반개, 즉 'H'인 경우의 횟수 ,알약 한개  즉 'W'인 경우의 횟수이다.

 

여기서, 모두 반조각을 먹는 경우는 1가지 경우 뿐이므로 미리 1로 DP를 채워둔다.

 

이를 이용하면 아래와 같은 코드가 나온다.

 

---

 

[코드]

 

import sys
input = sys.stdin.readline


while True:
    n = int(input())
    if n == 0:
        break
    dp = [[0 for j in range(n+1)] for i in range(n+1)]

    for i in range(n+1):
        dp[0][i] = 1

    for i in range(1,n+1):
        for j in range(i,n+1):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]

    print(dp[n][n])