[백준] 2225 합분해

문제

• 0부터 N까지의 정수 K개를 더해 그 합이 N이 되는 경우의 수 구하기
• 덧셈의 순서가 바뀌면 다른 경우로 센다
• 하나의 수를 여러 번 쓸 수 있다
• 1 <= N, K <= 200

 

풀이

• 전형적인 DP 문제다.
• dp[n][k] : N을 K개 수의 합으로 표현할 수 있는 개수
  • dp[0][0] = 1 이다. 
  • 숫자 1부터 N+1까지, 1개 ~ K개로 나타낼 수 있는 수를 구한다.
  • dp[n][k] = dp[n-1][k] + dp[n][k-1]
    k-1개를 더한 뒤 마지막 숫자를 L 이라고 할 때, 아래의 합이 dp[n][k]가 된다.
    L= 0; dp[n-0][k-1]
    L= 1 ; dp[n-1][k-1]
    L= 2; dp[n-2][k-1]
    ...
    L= n; dp[0][k-1] 
    
    즉, dp[n][k] = dp[n][k-1] + dp[n-1][k-1] + ... + dp[1][k-1] + dp[0][k-1] 이 된다.
    그리고 dp[n-1][k-1] + ... + dp[1][k-1] + dp[0][k-1] = dp[n-1][k] 로 일반화할 수 있다.

 

N, K = map(int, input().split())

# dp[n][k] : n을 k개 수의 합으로 표현할 수 있는 개수
dp = [[0] * (K+1) for _ in range(N+1)]
dp[0][0] = 1

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

 

References

• 백준 DP