백준 2294번 : 동전 2

Algorithm/problem

백준 2294번 : 동전 2 - dp C++

DingCoDing 2022. 3. 5. 21:56

https://www.acmicpc.net/problem/2294

2294번: 동전 2

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

www.acmicpc.net

#include <bits/stdc++.h>
using namespace std;

int n, k, arr[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;

	fill(arr, arr + 10001, INT_MAX);

	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;

		for (int j = 1; j <= k; j++) {
			if (j % num == 0) 
				arr[j] = min(arr[j], j / num);
                
			if(j-num >0 && arr[j-num]!=INT_MAX) 
				arr[j] = min(arr[j], arr[j - num] + 1);

		}

	}
	if (arr[k] == INT_MAX) cout << -1;
	else cout << arr[k];

	return 0;
}