백준 알고리즘 2225번 - 합분해

0부터 n까지 정수 k개를 더해서 그 합이 n이 되는 경우의 수.

dp를 사용하고, 점화식을 생각해보자.

정수 k개를 더해서 그 합이 n이 되는 경우는 정수 k-1개를 더해서 그 합이 n-L(0<=L<=n) 인 것으로 나눌 수 있다.

 

이해를 돕기위해 예를 들어보자.

정수 3개를 더해, 그 합이 5가 되는 경우를 생각해보자.

 

이를 이차원배열로 표현하면, dp[3][5]로 표현할 수 있고,

dp[3][5]=dp[2][5]+dp[2][4]+dp[2][3]+dp[2][2]+dp[2][1]+dp[2][0] 이라고 쓸 수 있다.

 

 

(마지막에 위치한 원소의 값을 1씩 늘려간다고 생각하면 편하다.)

이를 코드로 나타내면

for (int i = 1; i <= K; i++) 
		for (int j = 0; j <= N; j++) 
			for (int l = 0; l <= j; l++) 
				dp[i][j] += dp[i - 1][j - l] % 1000000000;

 

dp문제답게 처음 초기화를 해줘야하는데 정수 1개를 더해서 어떤 수를 만드는 방법은 항상 1개밖에 없다.(자기자신)

따라서 dp[1][n]는 항상 1이다.

 

또 정수 0개를 더해서 어떤 수를 만드는 방법은 없다.

처음 초기화할때 배열이 0으로 초기화되므로 0개를 더하는 경우는 배재하고, 1개를 더하는 경우는 아래와 같이 초기화해준다.

for (int i = 0; i <= N; i++)
		dp[1][i] = 1;

 

답은 k번 더해서 n을 만드는 것이므로 dp[k][n]이 답임을 알 수 있다.

 

 

코드

 

#include <iostream>

using namespace std;
long int dp[201][201]; // 자릿수, N의 합 경우 수 

int main()
{
	int N, K;
	cin >> N >> K;

	for (int i = 0; i <= N; i++)
		dp[1][i] = 1;

	for (int i = 1; i <= K; i++) 
		for (int j = 0; j <= N; j++) 
			for (int l = 0; l <= j; l++) 
				dp[i][j] += dp[i - 1][j - l] % 1000000000;

	cout << dp[K][N] % 1000000000;

	return 0;
}