2225 합분해

합분해 (2225)

 

문제

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

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

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

출력

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

예제 입력 1 복사

20 2

예제 출력 1 복사

21

 

---

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;
// 2225 합분해
const int MAX = 200;
const int MOD = 1000000000;


int main(){
	int N, K;
	// cache[k][n] k 개 더해서 합이 n
	int cache[MAX + 1][MAX + 1] = {1,};
	cin >> N >> K;
	

	for(int i = 1; i <= K; i++)
		for(int j = 0; j <= N; j++)
			for(int l = 0; l <= j; l++){
				cache[i][j] += cache[i - 1][j - l];
				cache[i][j] %= MOD;
			}
	cout << cache[K][N] << endl;
	
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

최적화 문제 동적 계획법 레시피

1. 모든 답을 만들어보고 최적해를 반환하는 완전 탐색 알고리즘을 설계
2. 전체 답의 점수를 반환하는 것이 아닌, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제의 정의를 바꿈.
3. 재귀 호출의 입력에 이전의 선택에 관련된 정보는 꼭 필요한 것만 남기고 줄인다.
4. 입력이 배열이거나 문자열이라면 적절한 변환을 통해 메모이제이션 하도록 한다.
5. 메모이제이션 적용 

 

풀이

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

 부분 문제의 정의를 바꾼다. 라는 말은 전체 답을 구하기 위한 전체 문제를 일정한 규칙 ( 점화식 ) 으로 쪼갠다는 말이다. 나의 임의대로 문제를 수정한다는 것이 아니다. 

처음 이 문제를 접근할 때 임의로 부분 문제를 수정하여 틀렸다. 레시피대로, 처음으로 완전 탐색 알고리즘을 설계해 보았는데 문제의 규칙과는 다른 완전 탐색 알고리즘을 구현하였다. 여기서부터 꼬였던 것이었다. 사실 완전 탐색 알고리즘 ( 점화식 구현) 을 하기만 하면 메모이제이션 자체는 어려운 것이 아니다. 

중요한 것은 최적해를 반환하는 완전 탐색 알고리즘 설계 를 어떻게 잘 하느냐이다. 이 문제를 겪어보면서 이것을 위해 좋은 방법은

1. 예제의 크기를 줄여서 단순화 시켜본다.

2. 직접 써보면서, 내가 수기로 답을 구해나가는 과정을 어떠한 문장이나 수식으로 정리한다.

3. 이를 토대로 완전 탐색 알고리즘을 구현한다.

4. 메모이제이션

https://velog.io/@embeddedjune/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-DP-2225-%ED%95%A9%EB%B6%84%ED%95%B4