백준 2294번 : 동전 2

문제 링크 : www.acmicpc.net/problem/2294

내 풀이(2021.1.18.) :

#include <iostream>
#include <algorithm>
#include <string.h>
#include <limits.h>

using namespace std;

int money[100]; // 단위 화폐
int dp[10001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k; cin >> n >> k;
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < n; i++) {
		cin >> money[i];
		if (money[i] < 10001) // out of index 방지
			dp[money[i]] = 1; 
	}

	for (int i = 1; i <= k; i++) {
		if (dp[i] == 1) continue; // 단위 화폐는 덮어쓸 수 없음
		int minim = INT_MAX;
		for (int j = 0; j < n; j++) {
			if (i - money[j] <= 0) continue; // out of index
			if (dp[i - money[j]] == -1) continue; // 만들 수 없는 수
			minim = min(minim, dp[i - money[j]] + 1);
		}
		if(minim != INT_MAX) dp[i] = minim;
	}

	cout << dp[k];

	return 0;
}

결과 : 성공

참고한 반례 : www.acmicpc.net/board/view/9847