출처 BOJ

합분해

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

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

출력

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

예제

풀이

정수K개를 더해서 N을 만드는 동작이 어떤형태인지 분해해보기.
ex) D[3][2] (정수3개 이용, 2 만들기)
= 2 + 0(D[2][0])
= 1 + 1(D[2][1])
= 0 + 2(D[2][2])
작은문제로 분할가능 + 분할된 문제가 전체를 구하는데 사용 → DP!
$D[K][N] = \sum_{n=0}^{N} D[K-1][n]$

범위체크

$\sum$부분에서 연속적으로 더해지면서 숫자 커짐
& 답%$10^9$으로 INT번위 초과할것이라고 유추가능
→ sum은 long long사용

코드

방법 code

#include<cstdio>
//#include<iostream>
#define MAX 1000000000;

using namespace std;

int D[201][201] = {0};

int search(int k, int value){
	long long sum = 0;
	if(k-1 != 0){
		for(int i = value; i >= 0; i--){
			if(D[k-1][i] == 0)
				sum += search(k-1,i);
			else
				sum += D[k-1][i];
			sum = sum % MAX;
		}
		D[k][value] = sum;
	}
	return D[k][value];
}

int main(){
	int N,K;
	scanf("%d%d",&N,&K);

	for(int i=0; i<201; i++){
		D[1][i] = 1;
		D[i][0] = 1;
	}
	
	printf("%d\n",search(K,N));
}

복잡도

memoization사용해서 연산횟수를 줄였으므로
→ $O(KN)$