[C++]BOJ 2293 - 동전 1

dp로 접근해서 풀어야 한다.
처음에 생각했던 방법은 dp[i]에 i원을 만들 수 있는 경우의 수를 저장하고, 각 dp[i]에 가지고 있는 동전의 종류(arr[j])원을 뺀 dp[i - arr[j]]를 더해주는 방법으로 풀면 되겠다고 생각했다.

<예제 1 입력>
3 10
1
2
5

<예제 1 출력>
10

막상 실행시켜보니 예제 1의 정답은 10이 나와야 하지만 내 코드는 128을 출력했다.

코드의 동작 과정을 생각해보면 오류가 보인다.
1원을 만들 때의 경우의 수 = 1개 (1)
2원을 만들 때의 경우의 수 = 2개 (1, 1 / 2)
여기서 내 코드의 논리로는 3원을 만들 때 1원(2원짜리 동전을 가지고 있으므로 3 - 2 = 1원)과 2원(1원짜리 동전을 가지고 있으므로 3 - 1 = 2원)의 경우의 수의 합과 같아야 한다.
따라서
3원을 만들 때의 경우의 수 = 3개 (1, 2 / 1, 1, 1 / 2, 1)
하지만 문제의 조건에서 순서만 다른 것은 같은 경우로 취급하라 했으므로 3원을 만들 때의 경우의 수에 동전의 조합이 중복되는 경우가 발생한다.
그래서 실제로 3원을 만들 때의 경우의 수는 2개이다. (1, 2 / 1, 1, 1)
아래 코드는 동전의 조합까지 모두 계산하는 결과를 출력한다.

#include <iostream>
using namespace std;
int n, k, arr[101], dp[10001];
int main() {
	cin >> n >> k;
	for(int i = 0; i < n; i++) {
		cin >> arr[i];
		dp[arr[i]] = 1;
	}
	for(int i = 1; i <= k; i++) {
		for(int j = 1; j < i; j++) {
			for(int a = 0; a < n; a++) {
				if(i - j == arr[a]) dp[i] += dp[j];
			}
		}
	}
	cout << dp[k];
}

물론 위의 코드는 오답처리를 받는다.

정답 처리를 받기 위해선 동전의 순서는 고려하지 않고 동전의 조합의 갯수만 출력하도록 작성해야한다.

그러기 위해 위의 예제의 경우 첫번째 동전만으로 경우의 수를 구하고, 두번째 동전까지 사용해 경우의 수를 구하고, 세번째 동전까지 사용해 경우의 수를 구하는 방법을 사용한다.
이 경우는 각각 동전들이 독립적인 결과를 가지므로 중복이 발생하지 않는다.
위의 코드와 대체로 유사하지만 dp[i]를 저장할 때 2중 for문에서 i와 j가 바뀐 형태다.

#include <iostream>
using namespace std;
int n, k, arr[101], dp[10001];
int main() {
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
		cin >> arr[i];
	dp[0] = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= k; j++) {
			if(arr[i] > j) continue;
			dp[j] += dp[j - arr[i]];
		}
	}
	cout << dp[k];
}

이 코드가 정답이다.