동전 1

알고리즘 구분 : 다이나믹 프로그래밍

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력
첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

예제 입력 1
3 10
1
2
5
예제 출력 1
10

문제 풀이

일단 바텀업방식으로 초반의 index에서 계산하였던 결과를 후반의 index에서 활용해야 한다고 판단하여, DP로 접근하였다.
그러나, 처음에는 dp[3] = (dp[0] dp[3]) + (dp[1] dp[2])와 같이, k를 만든다고 하면, k를 만들 수 있는 경우의 수를 찾아, 이들끼리의 곱을 더하는 방식으로 점화식을 구현해서 예제에 적용해보았으나 일치하지 않았다. 위의 점화식이 가지고 있는 오류는 아래와 같다.

n = 2, k = 4 / 동전 value : 1, 2
위와 같은 조건에서, dp[0] = 1, dp[1] = 1, dp[2] = 2, dp[3] = 2가 되어야 하는데, dp[2]값 자체가 위의 점화식에서 제대로 갱신되지 않았다. 또한 dp[4]를 구하는 과정에서 보았을 때, 동전의 가치가 1인 동전으로만 4를 만드는 경우의 수가 중복으로 더해져 dp[4]의 값이 원래 나와야 하는 결과보다 큰 값을 가진다.

내가 'X원'짜리를 활용해서 특정 금액을 만드는 과정이라면, 최소한 그 금액은 X원보다 크거나 같아야 한다. 예를 들어, 3원짜리 동전을 가지고 어떤 금액을 만들 때, 1원이나 2원을 만들 수 없다는 의미이다. 그 부분을 고려하여 점화식을 다시 만들게 되면, dp[Y] = dp[Y] - dp[Y - X]가 된다. 즉, X원을 활용해 Y원을 만들기 위해서는, Y - X원을 만드는 경우의 수를 더해주면 된다는 것이다. 이를 구현 과정에서 적용한다면, 이중 반복문을 사용하여, 첫 번째 반복문의 변수는 배열의 index를 지정하는 데 활용하며, 두 번째 반복문의 변수는 만들어가는 동전의 가치를 찾는데 활용한다.(즉, Y로 활용된다는 의미이다.)

시간복잡도를 단순하게 생각한다면, O(NK)가 되지만, 두 번째 반복문의 시작점이 0이 아닌 해당 index에서의 동전의 가치이기에, 실제 시간복잡도는 O(NK)보다 작을 것이다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<int> v(101);
int dp[10001];
void solve();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> k;
	for(int i = 1; i < n + 1; i++) {
		cin >> v[i];
	}
	
	solve();
	
	return 0;
}

void solve() {	
	dp[0] = 1;
	if(v[0] > k) {
		cout << 0 << endl;
	}
	else {
		for(int i = 1; i < n + 1; i++) {
			for(int j = v[i]; j < k + 1; j++) {
				dp[j] = dp[j] + dp[j - v[i]];
			}
		}
	}
	
	cout << dp[k] << endl;
}

• 문제 출처 : https://www.acmicpc.net/problem/2293
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.