BOJ 2294, 동전2

ProblemSolving · 03 Mar 2020

이 문제는 DP 문제입니다. 동전교환 문제죠.

풀이

비슷한 DP문제가 자주 나와서 다시 풀어봤습니다. 작년 ACM 예선문제에서도 같은 알고리즘 문제도 나왔었습니다.

이번에는 재귀함수를 이용해서 풀어봤습니다. 문제의 핵심은 k-dol[i] 라는 식인 것 같습니다.

k라는 돈이 남아있는데 dol[i]라는 동전이 필요한 경우를 모두 확인해주면 됩니다.

이 식만 세우면 완전탐색을 통해서 최솟값을 구할 수 있습니다.

#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<cmath>
using namespace std;
typedef long long ll;
int n,k,dol[101],dp[10001];
int go(int k)
{
	if (k == 0)
		return 0;
	int& ret = dp[k];
	if (ret != -1)
		return dp[k];
	ret = 1e9;
	for (int i = 1; i <= n; i++)
		if (k - dol[i] >= 0)
			ret = min(ret, go(k - dol[i]) + 1);
	return ret;
}
int main()
{
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++)
		scanf("%d", &dol[i]);
	memset(dp, -1, sizeof(dp));
	int ans = go(k);
	if (ans == 1e9)
		printf("-1");
	else
		printf("%d\n", ans);
	return 0;
}