BOJ 2225 합분해

문제출처 : https://www.acmicpc.net/problem/2225

1. 문제요약

- 0 부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수

- 1 + 2와 2 + 1은 다른 경우

- 숫자는 중복해서 사용 가능

- 1 <= N <= 200

- 1 <= K <= 200

2. 접근방법

- 숫자 N은 N-0 + 0

               N-1 + 1

               N-2 + 2

               N-3 + 3

               ...

               N-N + N

  으로 만들 수 있음

- d[n][k] : K번째 합이 N인 경우의 수라 하면

- d[n][k] = d[n-0][k-1] + d[n-1][k-1] + d[n-2][k-1] + ... + d[n-n][k-1]

3. 시간복잡도

- O(KN^2) = 8,000,000

4. 회고

- 합산 결과가 int를 넘는가?

- 재귀 리턴값이 옳바른가?

- mod 연산 할때

- <소스 2> 처럼 했었는데 틀리고 <소스 1>은 맞음

- <소스 2> : d[sum][cnt] = (A mod div + B mod div + ... N mod div) mod div 가 들어가고

  <소스 1> : d[sum][cnt] = (A mod div + B mod div + ... N mod div) mod div 가 들어가는데?

- 어라 근데 return d[sum][cnt] %= div 인데.. 연산자 우선순위 때문인가? 괄호 안쳐서 그런가?

  해봐야겠다

- <소스 1>은 맞고 <소스 2>가 틀린 이유는 '메모이제이션' 때문....

- <소스 1>의 d 배열에는 나머지 값이 들어가 있어서 line 6에서 정상적으로 나머지값이 반환됨.

- <소스 2>의 d 배열에는 나머지 값이 들어가 있지 않아서 line 6에서 나머지 연산 전의 값이 반환됨.

  <소스 2>의 line 6를 return d[sum][cnt] % div로 바꿔주면 정답

- <소스 2>의 line 11을 return d[sum][cnt] %= div로 바꿔주면 제일 빨리 수행됨

  나머지 연산이 덧셈 때 마다들어가지 않기 때문에

- 예를 들어 div = 5일 때,

  1 1 1   1 1 1   1 1 1

    3         3        3

              9 // <소스 1>은 9div5 = 4가 저장되고 / <소스 2>는 9가 저장됨

              ...

              12 // <소스 1>과 <소스 2> 모두 합은 4 + 4 + 4 이지만

                     <소스 1>은 12div5 = 2가 <소스 2>는 12가 저장됨

                      메모이제이션할때 저장된 값을 리턴하면

                     <소스 1>은 2를 <소스 2> 는 12를 리턴하므로 틀린 값이 나옴

                     그래서 <소스 2>의 line 6를 return d[sum][cnt] % div로 바꿔주면 정답이 됨.

long long dp(int sum, int cnt){
	if (cnt == 1)
		return 1;

	if (d[sum][cnt])
		return d[sum][cnt];

	for (int i = 0; i <= sum; i++){
		d[sum][cnt] += dp(sum - i, cnt - 1);
		d[sum][cnt] %= 1000000000;
	}

	return d[sum][cnt];
}

<소스 1>

long long dp(int sum, int cnt){
	if (cnt == 1)
		return 1;

	if (d[sum][cnt])
		return d[sum][cnt];

	for (int i = 0; i <= sum; i++)
		d[sum][cnt] += dp(sum - i, cnt - 1);

	return d[sum][cnt] % 1000000000;
}

<소스 2>

소스코드 : Top-Down

#include<iostream>
using namespace std;

int n, k;
long long d[201][201];

long long dp(int sum, int cnt){
	if (cnt == 1)
		return 1;

	if (d[sum][cnt])
		return d[sum][cnt];

	for (int i = 0; i <= sum; i++){
		d[sum][cnt] += dp(sum - i, cnt - 1);
		d[sum][cnt] %= 1000000000;
	}

	return d[sum][cnt];
}

int main(void){
	cin >> n >> k;
	cout << dp(n, k) << "\n";
	return 0;
}

소스코드 : Bottom-Up

#include<iostream>
using namespace std;

int n, k;
long long d[201][201];

int main(void){
	cin >> n >> k;
	d[0][0] = 1;

	for (int i = 1; i <= k; i++){
		for (int j = 0; j <= n; j++){
			for (int k = 0; k <= j; k++){
				d[j][i] += d[j - k][i - 1];
				d[j][i] %= 1000000000;
			}
		}
	}

	cout << d[n][k] << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]