[백준/C++] 2225. 합분해

문제

www.acmicpc.net/problem/2225

2225번: 합분해

유의사항

1+2 와 2+1을 다른 경우로 센다는 것. 

0도 사용할 수 있다는 것.

경우의 수를 1000000000으로 나눈 나머지를 출력해야한다는 것 

 

풀이

이 문제는 DP(동적 계획법)을 이용하면 풀 수 있다!

2차원 캐시배열을 이용한 메모이제이션을 적용해야 한다.

cache[k][n] : k개의 숫자를 더해서 n을 만들 수 있는 경우의 수 

 

그리고 cache[k][n]은 다음과 같이 구할 수 있다. (점화식) 

cache[k][n] = cache[k-1][0] + cache[k-1][1] + cacke[k-1][2] + ... + cache[k-1][n] 

 

코드

#include <iostream>
#include <vector>
using namespace std;
int N, K;
int cache[201][201] = { 0, }; // [k][n] k개의 수로 n을 만들 수 있는 경우의 수 저장 

int main(void) {
	cin >> N >> K;
	for (int i = 0;i <= N;i++) {
		cache[1][i] = 1; // 1개로 N을 만드는 경우의 수는 1개 (N자신)
	}
	for (int i = 0;i <= K;i++)
		cache[i][0] = 1; //i개로 0을 만드는 경우의 수는 1개 (0을 i개)
	for (int k = 2; k <= K; k++) {
		for (int n = 1; n <= N; n++) {
			for (int i = 0; i <= n; i++){
                cache[k][n] = (cache[k][n] + cache[k - 1][i]) % 1000000000;
            }
		}
	}
	cout << cache[K][N] << endl;
	return 0;
}

 

 

 

결과