[백준] 부녀회장이 될테야

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

2775번: 부녀회장이 될테야

 

0층일 때, dp = [1, 2, 3, 4, 5, 6, ...]

1층일 때, dp = [1, 3, 6, 10, 15, 21, ...]

2층일 때, dp = [1, 4, 10, 20, 35, 56, ...]

...

즉, 층이 올라갈 때 동적 계획법으로 구현해주면 된다. (dp[i] = dp[i-1] + dp[i])

 

import sys

T = int(sys.stdin.readline())

for i in range(T):
    dp = [j for j in range(1, 15)]
    k = int(sys.stdin.readline())
    n = int(sys.stdin.readline())
    
    for l in range(k):
        for m in range(1, n):
            dp[m] = dp[m-1] + dp[m]
    
    print(dp[n-1])