백준 Baekjoon 2294 동전2 풀이

사용언어

Visual studio 2019 C++

생각하기

다이나믹 프로그래밍

[2294 풀이]

#include <iostream>
#include <algorithm>
#include <cstring>

#define MAX 10001
#define endl "\n"
using namespace std;

int N, K;
int coin[101];
int sum[MAX];

int Coin() {
	memset(sum, 0, sizeof(sum));

	for (int i = 1; i <= K; i++)
		sum[i] = MAX;

	for (int i = 0; i < N; i++)
		for (int j = coin[i]; j <= K; j++)
			sum[j] = min(sum[j], sum[j - coin[i]] + 1);

	return sum[K] == MAX ? -1 : sum[K];
}

void init() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int main() {
	init();
	cin >> N >> K;

	for (int i = 0; i < N; i++)
		cin >> coin[i];

	cout << Coin() << endl;
}