백준 - 2225번(DP)

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

2225번: 합분해

import sys

n,k = map(int,sys.stdin.readline().split())

dp = [[0 for _ in range(201)] for _ in range(201)]

for i in range(201):
    dp[1][i] = 1 # k가 1일때는 n에 값에 상관없이 무조건 1가지 case만 가능
    dp[i][1] = i # n이 1일때도 무조건 k가지 case만 가능

for i in range(2,201):
    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]) #k개의 숫자로 n을 만들 수 있는 경우의 수

0~n까지의 숫자 중에 중복을 허용해서 k개를 뽑아서 합이 n이 되도록 하는 것이다.

dp문제를 잘 풀기 위해서는 답에 대한 점화식을 잘 세워야 한다. 이것이 DP의 전부이지만 그것이 매우 어렵다.

2차원 dp 배열을 보면 세로축은 k, 가로축은 n에 대한 값이다.

 

즉 k가 1일때는 n에 값에 상관없이 무조건 1가지 case만 가능하다.

그리고 n이 1일때도 무조건 k가지 case만 가능하다.

만약에 n = 1, k =6이라면 [1,0,0,0,0,0], [0,1,0,0,0,0]... [0,0,0,0,0,1] 이렇게 6가지가 된다.

이렇게 표를 채워나가다 보면

dp[i][j] = (dp[i][j-1]+dp[i-1][j])

이런 점화식을 찾을 수 있다.