[PS] BOJ2225 합분해 ( dp ) With python

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

2225번: 합분해

 

 

◎ 문제풀이

 

합해야 하는 K가 정해져 있어 어려운 문제였다. 

 

 

 

5가 되는 경우는 6가지가 있다.

 

0에 +5를 하는 경우

1에 +4를 하는 경우

2에 +3을 하는 경우

3에 +2를 하는 경우

4에 +1을 하는 경우

5에 +0을 하는 경우

 

k는 3이므로,

+0,+1,+2,+3,+4,+5은 2개의 합으로 구성되어야 한다. 이를 점화식으로 표현하면 아래와 같다.

 

dp[5][3] = dp[0][2] + dp[1][2] + dp[2][2] + dp[3][2] + dp[4][2] + dp[5][2] 

dp[n][k] = dp[0][k-1] + dp[1][k-1] + dp[2][k-1] + ... + dp[n-1][k-1] + dp[n][k-1]

 

여기서 

 

dp[n-1][k-1] = dp[0][k-1] + dp[1][k-1] + dp[2][k-1] + ... + dp[n-1][k-1]  이므로

 

dp[n][k] = dp[n-1][k-1] + dp[n][k-1] 

 

dp[n][k] 를 바텀업 방식으로 하나씩 채워나가며 답을 구하면된다.

 

 

 

◎코드

 

n,k = map(int,input().split())

dp = [[0]*(k+1) for _ in range(n+1)]
dp[0][0] = 1

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

print(dp[n][k]%1000000000)