[BOJ]2225. 합분해

문제:

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우) 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력:

첫째 줄에 두 정수 N(1<=N<=200),K(1<=K<=200)가 주어진다.

출력:

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

풀이방법:

동적계획법을 사용해서 이 문제를 풀었다. 점화식은 간단하다. K개의 합이 N이 되었을 때, 맨 마지막 수( l )를 빼면 남은 수는 K-1개로 N-l 이 남는 다는 것이다. 그래서 dp 테이블을 다음과 같이 구성할 수 있다.

dp[ i ][ j ] 는 i개의 수를 가지고 합이 j가 되는 경우를 뜻한다. 따라서 처음에는 1로 초기화되며, 한 층이 지날때마다 경우의 수가 더해져 우리가 원하는 dp[k][n]을 구할 수 있다.

n,k = map(int,input().split())
dp=[[0 for _ in range(n+1)]for _ in range(k+1)]
mod=1000000000
for i in range(n+1):
    dp[1][i]=1
 
for i in range(2,k+1):
    for j in range(n+1):
        for l in range(j+1):
            dp[i][j]+=dp[i-1][l]
        dp[k][n]%=mod
    
print(dp[k][n])

문제링크:

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

2225번: 합분해