[백준] 2225번 - 합분해 (C++)

 

2225번: 합분해

문제

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

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

 

 

입력

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

 

 

출력

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

 

 

풀이과정

해당문제는 "숫자 n을 k개의 수를 이용해서 만드는 경우의 수"를 구하라는 문제였었습니다.

n \ k	1	2	3	4
1	1	2	3	4
2	1	3	6	10

해당 문제에서 예제로 주어진 값들을 일단 쭈욱 구해보았더니

f[n][k] = f[n - 1][k] + f[n][k - 1] 형태로 다음에 해당하는 값이 나오고,

k가 1이면 경우의 수가 1개말고는 없으니 1이라는 값이 나오고 n이 1인 경우에는 k개의 수를 0과 1로만 구성을 한다면 그대로 k개의 수만큼만 만들 수 있다는 사실을 깨닫게 되어 해당정보들을 바탕으로 코드를 구성하였습니다.

 

 

code

#include <iostream>

long long dp[201][201];

int		main(void)
{
	int n, k;
	
	std::cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= k; j++) {
			if (j == 1 || i == 1)
				dp[i][j] = j;
			if (1 <= j - 1 && 1 <= i - 1)
			dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 1000000000;
		}
	}
	std::cout << dp[n][k];

	return (0);
}

 

후기

어찌저찌 값을 구해내기는 했는데.

이러한 근거를 통해서 값을 도출해내는것이 아니라 "아마 이런식으로 식을 전개하다보면 이렇게 나오지않을까?" 하고

어림짐작해서 문제를 푸는 과정이 되어 아쉬움이 많이 남는 거 같다.

수학을 더 공부를 해봐야하나..