[python] 백준 4811 알약

https://www.acmicpc.net/problem/4811

 

문제 해결

• DP를 이용해야하는 문제라는 것은 쉽게 알 수 있다.
• 그런데 DP를 어떻게 활용할지는 생각보다 어렵다.
• 힌트는 알약이 $n$개가 있으면 H가 $n$번 W가 $n$번 써진다는 사실이다.
• 그래서 dp[i][j]를 H가 $i$번, W가 $j$번 썼다는 것으로 정의한다.
• j가 1~n일 때 dp[0][j]는 1이다.
• 그리고 dp[i][j] += dp[i-1][j] + dp[i][j-1]이다.

 

CODE

import sys
input = sys.stdin.readline


def DP(n):

    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
    for i in range(1,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]

    return dp[n][n]

if __name__ == "__main__":

    while True:
        n = int(input())
        if n==0:break

        ans = DP(n)
        print(ans)