백준 Gold 5 합분해

합분해 (백준 Gold 5)

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

0~N 까지의 정수를 k개 더하여 그 합이 N이 되는
경우의 수를 구하는 프로그램

풀이 방법

중복된 값을 이용하는 것이 보였으므로 dp를 이용하였다
그리고 top - down 방식으로 풀었다

점화식을 세우자면
dp[n][k] : k개를 더하여 n이 되는 경우의 수

기저 조건
dp[n][0] = 0 : 0개를 더하여 가능한 수는 없음
dp[n][1] = 1 : 1개를 고른다면 자기 자신 밖에 없음

또한 각 수들은
0 + n, 1 + n - 1, 2 + n-2, …, n - 1 + 1, n + 0 같이
순서가 바뀌어도 셀 수 있음

• 특정한 한 자리의 값이 i라면 나머지는 n-i가 되어야
  n이 된다
  

• 여기에 k번째 수임을 고려한다면
  i 가 결정되었을때 k-1에 대한 수로 n-i를 구해야 함
  

• 따라서 반복문의 i로 수를 고정시키고
  다시 재귀를 돌려 n - i 가 k-1 로 만들어지는 경우의수를 구함
  

• dp[n][k]는
  

  0~n 까지의 k-1의 합
  dp[n][k] = for(i : 0 ~ n) dp[i][k-1]
  (사실 dp[n-i][k-1]이 더 위의 식의 의미에 걸맞긴 하다)
  

제출 코드

#include<iostream>
#include<vector>

using namespace std;

const int divV = 1000000000;

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

long recur(int n,int k)
{
	if (k == 0)
		return 0;

	if (k == 1)
		return 1;

	if (dp[n][k] != 0)
		return dp[n][k];

	for (int i = 0; i <= n; i++)
	{
		dp[n][k] += recur(i, k - 1);
		dp[n][k] %= divV;
	}

	return dp[n][k] % divV;
}

int main()
{
	int n, k;
	cin >> n >> k;

	cout << recur(n,k);

	return 0;
}

결과

divv로 값을 나누지 않고,
또 int의 오버 플로우일 가능성이 있어
그냥 안전하게 long으로 선언하니
해결되었다