2294번 동전 2

서재혁·2022년 8월 15일

백준

DP

목록 보기

4/6

문제

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

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

입력

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

출력

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

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N, money;
vector<int> vi;
int mp[10001] = { 0, };

void solve()
{
	cin >> N >> money;
	int num;
	for (int i = 0; i < N; i++)
	{
		cin >> num;
		vi.push_back(num);
	}
	mp[0] = 0;
	for (int i = 1; i < 10001; i++)
		mp[i] = 100000;
	for (int i = 0; i < N; i++)
	{
		for (int j = vi[i]; j <= money; j++)
		{
			if(mp[j] > mp[j - vi[i]] + 1)
				mp[j] = mp[j - vi[i]] + 1;
		}
	}
	if (mp[money] != 100000)
		cout << mp[money];
	else
		cout << -1;
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
	return 0;
}