[2225] 합분해

• 입력: 표현하려는 숫자 N(1≤N≤200), 양수의 개수 K(1≤K≤200)
• 출력: 자연수 N을 K개의 양수로 표현할 수 있는 방법의 수(숫자 순서가 다르면 다른 경우)
• 알고리즘: 동적 계획법
• 소스코드
#define _CRT_SECRUE_NO_WARNINGS #include <cstdio> #include <vector> #define MOD 1000*1000*1000 using namespace std; vector<vector<int> > cache; int sumDecomp(int n, int k) { if (n < 0 || k <= 0) return 0; int& ret = cache[n][k]; if (ret != 0) return ret; for (int i = 0; i <= n; i++) ret = (ret + sumDecomp(n - i, k - 1))%1000000000; return ret; } int main() { int n, k; scanf("%d%d", &n, &k); cache = vector<vector<int> >(n + 1, vector<int>(k + 1, 0)); //첫 번째 인자 - 만들고자 하는 숫자, 두 번째 인자 - 표현 갯수 for (int i = 0; i <= n; i++) cache[i][1] = 1; printf("%d\n", sumDecomp(n, k)); return 0; }

간단히 예를 들면 4로 3개의 양수로 표현하는 방법(이하 [4,3]이라 표현)을 설명을 하면 다음과 같다.

우선, 모든 숫자는 1개의 양수로 표현할 수 있는 방법은 1가지씩 갖고 있다. 

4 = 0 + [4,2] 호출 

  = 1 + [3,2] 호출

  = 2 + [2,2] 호출

  = 3 + [1,2] 호출

  = 4 + [0,2] 호출

이때, [4,2]에서 반복적으로 [4,1],[3,1],[2,1],[1,1],[0,0]을 호출한다. 총 5개이다.

문제를 풀면서 알았는데, 똑같은 숫자가 여러번 나와도 되는 모양이다.

• 문제 참조: https://www.acmicpc.net/problem/2225