[백준][2225] 합분해

문제

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

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

입력

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

출력

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

입력 1

20 2

출력 1

21

1. 문제 설명

• 위 표와 같이 크게 2가지 방법으로 풀 수 있다.
• K=2이고, N=3일 때의 경우의 수는 어떻게 구할 수 있을까?
  1. K=1일 때, N = 0부터 N까지 더하여 경우의 수를 구하는 방법.
     (파란색 선택 / 삼중 for문으로 구현 가능)
  2. K=1이고 N=1일 때와 K=2이고 N=2일때를 더하여 경우의 수를 구하는 방법.
     (초록색 선택 / 이중 for문으로 구현 가능)
• dp[k][n]의 값 : 정수 k개를 더해서 n이 되는 경우의 수

1-1. 파란색 표시 방식 (삼중 for문)

• 위 그림을 설명해 보자면, 합 N을 만들기 위해서 0 ~ N 까지의 정수를 사용해야한다. 그 중 마지막 수를 L이라고 가정한다.
  그렇다면 L 이전의 수들의 합은 N-L이라는것을 알 수 있으며, 총 K개에서 L인수를 제외하기 때문에 수의 개수는 K-1이 된다.
  그러므로 dp[k-1][0] 부터 dp[k-1][n] 까지 더해주면 되는것이다!

• 이해가 안 될 수 있다! 본인도 이해 하지 못했었다.. ㅠㅠ

• 위 그림은 K가 3이고 N이 3인 수(dp[3][3])을 구해보는 예시이다.
  (파란색은 해당 경우의 식, 분홍색은 경우의 갯수이다.)

  1. 1개의 수로 3까지 구할 수 있는 경우를 센다.
     (k=1 일때, n은 자기자신만 더해야 하기때문에 k=1일때 경우의 수는 모두 1이다.)
  2. 2개의 수로 3까지 구할 수 있는 경우를 센다.
  • 이 부분에서 눈에 띄는 규칙이 있다. dp[2][2]를 예로 들면, dp[1][0], dp[1][1], dp[1][2]를 더한 값이 경우의 수가 된다.
    3. 이 규칙을 적용하면 결국 dp[3][3]은 2개의 정수를 더해 만들어진 0의 경우 + 3, 2개의 정수를 더해 만들어진 1의 경우 + 2, 2개의 정수를 더해 만들어진 2의 경우 + 1, 2개의 정수를 더해 만들어진 3의 경우 + 0 최종적으로 해당 경우의 수들을 모두 더한 값이 경우의 수가 되는것이다.
    (그림에 dp[3][3]은 없다. 한번 직접 적어가면서 이해해보시라는 소리다..^^ㅎㅎ)

1-2. 초록색 표시 방식 (이중 for문)

꼭! 위에 파란색 표시 방식을 읽고 내려오셔야 이해가 된다.

• 파란색 표시 방식을 이해했다면 대충 알 수 있을 것이다. 이 방식은 어느정도 경우의 수를 구하여 쭈르륵 나열을 하면 규칙성이 보인다.
  (사실 위 경우처럼 규칙성을 찾을 수도 있으나 설명하기가 너무 어렵다..)

• 개인적으로 이분의 설명이 깔끔하다고 생각하여 해당 글을 참고해주길 바란다.
  도랑도랑해 님의 2225번 문제 풀이 링크

2. 소스코드

[1-1]방식의 소스코드

int main() {
	int n, k;

	cin >> n >> k;

	vector<vector<long long> > dp(k + 1, vector<long long>(n + 1, 0));

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

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

	cout << dp[k][n] << endl;
}

[1-2]방식의 소스코드

#include <iostream>
#include <vector>

const long long MOD = 1000000000;

using namespace std;

int main() {
	int n, k;

	cin >> n >> k;

	vector<vector<long long> > dp(k + 1, vector<long long>(n + 1, 0));

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

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

	cout << dp[k][n] << endl;

	return 0;
}