[백준]2294 동전2 (수정 + 최적화)

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

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

입력

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

 

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

골드5 DP문제입니다.

배열 arr[i][j]는 i번째 동전까지 사용해서 j원을 만들 수 있는 최소 동전 개수입니다.

	#include<bits/stdc++.h>
	
	using namespace std;
	int arr[101][10001];
	vector<int>coins;
	int main() {
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);
		memset(arr, -1, sizeof(arr));
		int n, k, x;
		cin >> n >> k;
		for (int i = 1; i <= n; i++) {
			cin >> x;
			coins.push_back(x);
		}
		sort(coins.begin(), coins.end());
		coins.erase(unique(coins.begin(), coins.end()), coins.end());

		for (int i = 0; i < coins.size(); i++) {
			if (i == 0) {
				for (int j = 1; j <= k; j++) {
					j % coins[i] == 0 ? arr[i][j] = j / coins[i] : arr[i][j] = -1;
				}
			}
			else {
				for (int j = 1; j <= k; j++) {
					if (j % coins[i] == 0)
						arr[i][j] = j / coins[i];
					else {
						int temp = INT_MAX;
						for (int k = 0; k <= j / coins[i]; k++) {
							if (arr[i - 1][j - k* coins[i]] != -1)
								temp = min(temp, k + arr[i - 1][j-k*coins[i]]);
						}
						if (temp == INT_MAX)
							arr[i][j] = arr[i - 1][j];
						else
							arr[i][j] = temp;
					}
				}
			}
		}
		cout << arr[coins.size() - 1][k];
	}

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

2022-12-28

#include<iostream>
#define INTMAX 1000001
using namespace std;
int dp[10001], n, k, x;
int main() {
	cin >> n >> k;
	for (int i = 1; i <= k; i++)
		dp[i] = INTMAX;
	while (n--) {
		cin >> x;
		for (int i = x; i <= k; i++) 
			dp[i] = min(dp[i], dp[i-x] + 1);
	}
	dp[k] == INTMAX ? cout << -1 : cout << dp[k];
}

dp[i]는 동전 x까지 사용했을때, 최소 동전입니다. 동전x를 하나 사용했을때, dp[i-x]+1와 기존값 dp[i]를 비교해 작은 값을 저장합니다.