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

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

2294번: 동전 2

#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;
}

백준 2294