[백준] 합분해

출처:: www.acmicpc.net/problem/2225

분류:: dp

 

1. 문제 이해 및 해결과정

- 0 ~n까지 정수 k개 더해서 합이 n이 되는 경우 ex) 6 2  => 0 1 2 3 4 5 6  0 6 ,1 5,2 4,3 3 , 6 0, 5 1 ,4 2   dp[k][n] =k개를 더해서 합이 n인 경우  dp 0 1 2 3 4 5  0  1 0 0 0 0 0  //배열만들기 위해  1  1 1 1 1 1 1       ex) dp[1][4] = 4를 1개의 수로 만들 수 있는 경우의 수 4  2  1 2 3 4 5 6       ex) dp[2][2] = 2를 2개로 만들 수 있는 경우의 수 2+0. 0+2, 1+1  3  1 3 6 10 15 21  ex) dp[3][1] = 1을 3개로 만들 수 있는 경우의 수 1+0+0 ,0+1+0, 0+0+1 =>dp[k][n] = dp[k][n-1] + dp[k-1][n]

 

2. 풀이방법

 1. [ python] dp

#합분해
#https://www.acmicpc.net/problem/2225
import sys
sys.stdin = open("input.txt","r")
n,k=map(int,input().split())
dp=[[0]*(n+1) for _ in range(k+1)]
mod=int(1e9)
dp[0][0]=1
for i in range(1,k+1):
    dp[i][0]=1
    for j in range(n+1):
        dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod
print(dp[k][n])

 

3. 오답원인

 

4. 알게된 점