백준 2225번 : 합분해

  사실 함수를 새로 만들어서 재귀처럼 풀 필요도 없이 그냥 3중 for문으로 풀어도 되긴하지만 이렇게 함수로 기능을 분리하는 것이 내가 읽기도 쉽고 내 취향이라서 이렇게 풀었다. count(n, k)라는 함수는 k개의 숫자로 n을 만드는 경우의 수를 출력해주는 함수다. 그렇다면 어떻게 점화식을 세울 것인가? 나는 k를 기준으로 점화식을 세웠다.

 

n을 만들기 위해 마지막으로 더한 숫자가 0이라면? 그 전까지는 k-1개의 숫자로 n을 만든다 = count(n, k-1)

n을 만들기 위해 마지막으로 더한 숫자가 1이라면? 그 전까지는 k-1개의 숫자로 n-1을 만든다 = count(n-1, k-1)

 

(생략)

 

n을 만들기 위해 마지막으로 더한 숫자가 n-1이라면? 그 전까지는 k-1개의 숫자로 1을 만든다 = count(1, k-1)

n을 만들기 위해 마지막으로 더한 숫자가 n이라면? 그 전까지는 k-1개의 숫자로 0을 만든다 = count(0, k-1)

 

  따라서 count(n, k)는 count(n, k-1)부터 count(0, k-1)까지 더한 것이다! 이것을 고상하게 식으로 쓰면 이렇게 된다.

고상한 시그마를 사용해보자 ^^

  그리고 이것을 코드로 표현하면 끝~

 

#include <stdio.h>
#include <iostream>
 
using namespace std;

int mod = 1000000000;
long long sum[204][204];

long long count(int n, int k)
{
    if(sum[n][k] != 0) return sum[n][k];
    
    long long ret = 0;
    for(int i = 0; i <= n; i++)
    {
        ret += count(n - i, k - 1);
    }
    
    sum[n][k] = ret % mod;
    return sum[n][k];
}

int main()
{
    int n, k;
    cin >> n >> k;
    
    for(int i = 0; i <= n; i++)
    {
        sum[i][1] = 1;
    }
    
    
    cout << count(n, k) << "\n";
 
    return 0;
}