[C++]BOJ 2294 - 동전 2

처음 생각했던 방법은 dp[i]에 i원을 만들기 위한 동전의 최소 갯수를 저장하는 방식으로 현재 i보다 작은 j원을 순차로 돌며 i - j원 짜리 동전이 있나 확인한 후, dp[i]에는 그 중 가장 작은 값을 넣도록 작성했다.

실제로 돌려보니 시간초과를 받았다.
최악의 경우에서 i * j * n == 10,000 * 10,000 * 100 == 백 억 번을 반복하기 때문이다.

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

위의 코드는 시간초과가 발생한다.

이 문제를 해결하기 위해 동전 1 문제 처럼 첫 번째 동전만 사용 했을 때의 최소값과 두 번째 동전까지 사용 했을 때의 최소값과 … 이런식으로 마지막 동전까지 모두 사용했을 때의 최소값을 구하면 dp[k]에 k원을 만들 때 필요한 동전의 최소 갯수가 들어간다.

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

99999는 10000보다 크기 때문에 절대 나올 수 없다.