백준 2225번 합분해

문제 링크입니다: https://www.acmicpc.net/problem/2225

K개의 숫자로 N을 구성하는 방법은 K-1개의 숫자로 N-K를 구성하는 방법들의 합이란 것을 이해한다면 쉽게 코드를 작성할 수 있는 문제였습니다.

/*

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

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1 + 2와 2 + 1은 서로 다른 경우).

또한 한 개의 수를 여러 번 쓸 수도 있다

*/

#include <iostream>

#include <cstring>

using namespace std;

 

const int MAX = 200;

const int MOD = 1000000000;

 

int N, K;

int cache[MAX + 1][MAX + 1]; //N, K

 

int numOfSum(void)

{

        memset(cache, 0, sizeof(cache));

        for (int i = 0; i <= N; i++)

               cache[i][1] = 1; //K=1인 경우 1가지

 

        //마지막 수를 k라 가정

        //k 이전의 수들의 합은 N-k

        //따라서 i개의 숫자로 N을 구성하는 방법은

        //(i-1)개의 숫자로 N-k를 구성하는 방법들의 합

        for (int i = 2; i <= K; i++)

               for (int j = 0; j <= N; j++)

                       for (int k = 0; k <= j; k++)

                              cache[j][i] = (cache[j][i] + cache[j - k][i - 1]) % MOD;

        return cache[N][K] % MOD;

}

 

int main(void)

{

        cin >> N >> K;

        if (N<1 || N>MAX || K<1 || K>MAX)

               exit(-1);

 

        cout << numOfSum() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~