[백준 - 2225] 합분해
숫자 하나를 더 넣는 경우와 합을 하나 줄이는 경우로 점화식을 만든 조합 DP 풀이.
2022년 9월 2일
합이 n이 되도록 k개의 0 이상의 정수를 고르는 경우의 수를 구한다. 마지막 수가 0인 경우와 0보다 큰 경우로 나누면 점화식이 단순해진다.
dp[n][k] = dp[n][k - 1] + dp[n - 1][k]- 마지막 수가 0이면
n을k - 1개로 만드는 경우다. - 마지막 수가 1 이상이면 마지막 수에서 1을 빼
n - 1을k개로 만드는 경우와 대응된다.
0을 만드는 방법과 하나의 수로 만드는 방법을 1로 초기화한 뒤 표를 채웠다.
문제: 2225 합분해 · 코드: GitHub에서 보기