문제 링크

합분해

문제 설명

0~N까지 K개의 숫자를 더해서 합이 N이 되게 하는 경우의 수를 구하라. 단, 덧셈의 순서가 바뀐 경우는 다른 경우(1+2랑 2+1는 다름)이고, 하나의 수를 여러번 쓸 수 있다.

문제 풀이

1. 상태 정의하기

$dp[i][j]$ = i를 만들기 위해 숫자 j개 더하기

K=2일때,

• N = 20 이면 (예시로 주어진 tc)
  (0,20), (1,19), (2,18), ..., (19,1),(0,20) -> 총 21개
• N = 3 이면
  (0,3), (1,2), (2,1), (3,0) -> 총 4개

--> N+1개

K=3,

• N = 2이면
  (0,0,2), (0,2,0), (2,0,0)
  (0,1,1), (1,0,1), (1,1,0)
• N = 3이면,
  (0,0,3), (0,3,0), (3,0,0)
  (0,1,2), ...
  (1,1,1)

표를 그려보면,

i=1인 경우, dp[1][j] = 1을 만들기 위해서 j개 더하기 -> 항상 j개
j=1인 경우, dp[i][1] = 1개로 i 만들기 -> 항상 1개
를 제외하고 i>=2, j>=2에 대해서 $dp[i][[j] = dp[i-1][j] + dp[i][j-1]$을 만족함을 알 수 있다.

2. 코드

import sys
from itertools import product

input = sys.stdin.readline

N, K = map(int, input().split())
dp = [[0]*(K+1) for _ in range(N+1)]

for i in range(N+1):
    dp[i][1] = 1

for i in range(K+1):
    dp[1][i] = i

for i in range(2, N+1):
    for j in range(2, K+1):
        dp[i][j] = (dp[i-1][j]+dp[i][j-1]) % 1000000000

print(dp[N][K])

참고

https://it-garden.tistory.com/341