[백준] 2294번 동전2 C++

문제 출처: https://www.acmicpc.net/problem/2294

2294번: 동전 2

(현재 쓸 인덱스, 현재 k)를 매개변수로 갖는 재귀함수를 작성한다.

인덱스 0번부터 동전을 0~최대로 사용한 뒤 다음 인덱스로 넘겨준다.

다음 인덱스도 마찬가지로 0~최대로 사용한 뒤 다다음 인덱스로 넘겨주며

최종적으로 인덱스가 N이되면 즉, 모든 인덱스에 대해 0번 이상의 코인을 사용할지 말지를 거쳐온 후

K가 0이 아니라면 오답이므로 큰 값을 넣어주어 나중에 작은 값으로 갱신될 수 있도록 한다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>

using namespace std;

int cost[101];
int dp[101][10001];
int MAX = 123456789;
int N, K;

int rec(int now, int k) {
	//끝한칸 뒤 idx까지 도착했지만 k를 전부 사용 못한경우 불가능
	if (now == N) {
		if (k == 0)return 0;
		else return MAX;
	}

	if (dp[now][k] != -1)return dp[now][k];

	//현재 idx의 코인을 하나도 안쓰고 다음 idx로 넘김
	int result = rec(now + 1, k);

	//현재 idx를 하나 쓰고 현재 idx로 넘김
	if (k >= cost[now])result = min(result, rec(now, k - cost[now]) + 1);
	dp[now][k] = result;
	return dp[now][k];

}

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

	cin >> N >> K;

	for (int i = 0; i < N; i++) {
		cin >> cost[i];
	}

	fill(&dp[0][0], &dp[100][10001], -1);

	int ret = rec(0, K);
	if (ret == MAX)cout << "-1";
	else cout << ret;

}