백준 2294번: 동전 2

[문제 링크]

2294번: 동전 2

---

https://onlytrying.tistory.com/89 동전 1의 변형 문제였다.

 

입력받은 동전의 가치를 배열 coin[n]에 저장할 때, k원을 만드는 동전의 최소 개수는 i = 1~n까지 k-coin[i]원을 만드는 최소 개수가 가장 작은 개수 + 1이다.

 

k원을 만들지 못하는 경우 -1을 출력해줘야 하기 때문에 top-down에서는 기저사례로 k가 0보다 작을 때 무한대(INF)를 반환하도록 하였고, bottom-up에서는 초기값을 무한대(INF)로 초기화하였다.

---

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

const int INF = 987654321;
int n, k, coin[101], memoTop[101][10000], memoBot[10000];

inline int min(int a, int b) { return a < b ? a : b; }

int Topdown(int start, int k)
{
	if (k <= 0) return k == 0 ? 0 : INF;

	int& ret = memoTop[start][k];
	if (ret != -1) return ret;

	ret = INF;
	for (int i = start; i <= n; i++)
		ret = min(ret, Topdown(i, k - coin[i]) + 1);

	return ret;
}

int Bottomup(int k)
{
	for (int i = 1; i <= k; i++)
	{
		memoBot[i] = INF;
		for (int j = 1; j <= n; j++)
			if (i - coin[j] >= 0)
				memoBot[i] = min(memoBot[i], memoBot[i - coin[j]] + 1);
	}
	
	return memoBot[k] == INF ? -1 : memoBot[k];
}

int main(void)
{
	cin >> n >> k;

	for (int i = 1; i <= n; i++)
		cin >> coin[i];

	// top-down
	memset(memoTop, -1, sizeof(memoTop));
	int res = Topdown(1, k);
	if (res == INF)
		cout << -1 << endl;
	else
		cout << res << endl;

	// bottom-up
	cout << Bottomup(k) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 83 day