백준 2225번: 합분해

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

2225번: 합분해

 

 

 

 

 

문제

 

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

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

 

 

 

입력

 

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

 

 

 

출력

 

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

 

 

 

 

 

5를 만드는 방법을 생각해보자.

 

5를 정수 2개로 만드는 방법은 총 6개가 있다.

0+5, 1+4, 2+3, 3+2, 4+1, 5+0

 

5를 정수 3개로 만드는 방법은 아래와 같다.

0+0+5, 0+1+4, 0+2+3, 0+3+2, 0+4+1, 0+5+0

1+0+4, 1+1+3, 1+2+2, 1+3+1, 1+4+0

2+0+3, 2+1+2, 2+2+1, 2+3+0

3+0+2, 3+1+1, 3+2+0

4+1+0, 4+0+1

5+0+0

 

 

dp[n][k]이 정수 k개를 합쳐서 n을 만드는 경우의 수라고 하면 아래와 같은 식을 통해 정수 3개를 더해 5를 만드는 경우의 수를 구할 수 있다. 

 

dp[5][3]=dp[5][2]+dp[4][2]+dp[3][2]+dp[2][2]+dp[1][2]+dp[0][2]

 

 

 

 

 

이를 일반화하면 다음과 같다.

 

 

for(int i=1; i<=n; i++){
     for(int j=1; j<=k; j++)
          dp[i][j]=(dp[i-1][j]+dp[i][j-1]);
}

 

 

 

 

코드

#include <stdio.h>

int main(void){
	int n, k; // 0 ~ n까지의 정수 k개를 더해서 그 합이 n이 되는 경우의 수
	scanf("%d %d", &n, &k);

	int dp[201][201]={ 0, };

	// 초기화
	for(int i=1; i<=k; i++)
		dp[0][i]=1;
	

	for(int i=1; i<=n; i++){
		for(int j=1; j<=k; j++)
			dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000000; 
	}

	printf("%d\n", dp[n][k]);
}