[2294] 동전 2

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

2294번: 동전 2

문제

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

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

입력

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

출력

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

코드

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>

using namespace std;
const int INF = 999999;

int n, k;
vector<int> money;
int cache[101][10001];
int memoBot[10000];

int dp(int pick, int price){
	
	if(price == 0){
		return 0;
	}

	if(price < 0){
		return INF;
	}

	int& ret= cache[pick][price];

	if(ret != -1){
		return ret;
	}

	ret = INF;
	
	for(int i=pick; i<n; ++i){
		ret = min(ret, dp(i, price-money[i]) + 1);
	}

	return ret;
}

int bottomUp(){
	for(int i=1; i<=k; ++i){
		memoBot[i] = INF;
		for(int j = 0; j<n; ++j){
			if(i-money[j] >= 0){
				memoBot[i] = min(memoBot[i], memoBot[i-money[j]] + 1);
			}
		}
	}
}

int main(void){
	memset(cache, -1, sizeof(cache));
	int minn = 9999;
	cin >> n >> k;

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

	int ans = dp(0, k);

	if(ans == INF){
		cout << -1;
	}

	else{
		cout << ans;
	}
	
}

오랜만에 dp 문제를 풀어봤다.

bottom-up 방식과 top-down 방식을 둘다 사용해봤는데

먼저 bottom-up방식은 재귀를 활용한 방법으로써 위에선 cache배열에 인자로 뽑을 동전의 종류(pick)와  남은 가격(price)를 인자로 줬다.

그래서 만약 INF를 리턴하면 한번도 price가 0이 된 적이 없으므로 -1을 출력한다.

top-down 방식은  dp배열 (여기선 memoBot)을 만들어서 0부터 15까지 쭉 나열한다음 한번 값을 써본다.

그리고 값들에서 규칙을 찾아 점화식을 만들어서 코드로 작성해주는 방식으로 만들어 주면 된다.

아직 top-down 방식에 익숙치가 않아 좀 더 공부가 필요할 듯 하다.