[백준/BOJ] 백준 2294번 : 동전 2

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

2294번: 동전 2

지금까지 고른 동전 가치의 합이 sum일 때 동전 가치의 합을 k원이 되도록 만들기 위해 필요한 최소 동전 개수를 리턴하는 함수를 만들었다. 동전을 고르다 보면 고른 동전 가치의 합이 sum인 경우가 중복해서 나올 수 있는데 이때는 이전에 계산했던 값을 사용한다. 왜냐하면 각각의 동전을 몇개라도 사용할 수 있으므로 이전에 어떤 동전을 골랐었는지는 동전 선택에 영향을 주지 않고 현재 고른 동전 가치의 합인 sum만이 결과에 영향을 주기 때문이다.

 

코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int n, k;
vector<int> coin;
int cache[10000];

//지금까지 고른 동전 가치의 합이 sum일때 동전 가치의 합을 k원이 되도록 만들기 위해 필요한 최소 동전 개수
int Solve(int sum)
{
	//기저사례(동전 가치의 합이 k일때)
	if (sum == k)
		return 0;

	//동전 가치의 합이 k를 넘어서면 k를 만들 수 없으므로 매우 큰 수를 리턴한다
	if (sum > k)
		return 987654321;

	int& ret = cache[sum];

	//고른 동전 가치의 합이 sum인 경우를 계산한 적이 있을때
	if (ret != -1)
		return ret;

	ret = 987654321;

	//각각의 동전을 몇개라도 사용할 수 있으므로
	//이전에 어떤 동전을 골랐었는지는 동전 선택에 영향을 주지 않는다
	for (int i = 0; i < coin.size(); i++)
	{
		ret = min(ret, Solve(sum + coin[i]) + 1);
	}

	return ret;
}

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

	int temp;
	int result;

	memset(cache, -1, sizeof(cache));

	cin >> n >> k;

	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		coin.push_back(temp);
	}

	result = Solve(0);

	//987654321을 리턴하면 동전 가치의 합을 k로 만들 수 없는것이다
	if (result == 987654321)
		result = -1;

	cout << result;

	return 0;
}