백준[2225]python

문제 :

이 문제는 다이나믹 프로그래밍 통해 해결해야 하는 문제이다.

하나씩 생각을 해보자.

1부터 시작해보면... 열이 n이고 행을 k로 놨을 때 k가 1일 때 n을 만족하는 것은 무조건 자기 자신인 경우밖에 없기 때문에 1이다.

k가 2가 되면 n의 값보다 n+1개의 경우의 수가 발생한다.

한 번만 더 해보자.. k가 3이 되면 3,6,10,15이 되고, 써놓고 보니 점화식을 구할 수 있었다.

arr[i][j] = a[i-1][j] + a[i][j-1] 

위의 식을 그대로 구현해주기만 하면 이 문제는 간단하게 해결할 수 있다. 

	1	2	3	4
1	1	1	1	1
2	2	3	4	5
3	3	6	10	15

import sys


if __name__ =='__main__':
    input = lambda : sys.stdin.readline().strip()
    n,k = map(int,input().split())
    dp = [[0]*201 for i in range(201)]
    for i in range(201):
        dp[1][i] = 1
        dp[2][i] = i+1
    
    for i in range(2,n):
        dp[i][1] = i
        for j in range(2,201):
            dp[i][j] = (dp[i][j-1] + dp[i-1][j]) %1000000000
    print(dp[k][n])