[PS][DP] 14916 : 거스름돈

[2021년 08월 08일 17시 04분 작성]

 

[PS][DP]
14916 : 거스름돈

---

[문제 링크 : (클릭)]

---

1. 풀이

 

기초적인 DP 문제입니다.

점화식을 아래와 같이 세우고, 코드로 옮겨주면 해결할 수 있습니다.

DP(k) =   INF   (k<=0)       　 　 1   (k==2 or k==5)               min(DP(k-2), DP(k-5)) + 1;  (else)

 

+) 하나 유의해야 할 점은 있습니다. 바로, 주어진 2원 5원 동전으로 거슬러줄 수 없는 경우가 있습니다.

    이럴 떄에는 DP(k) 값이 INF를 넘어서기 때문에 이를 조건문으로 잘 걸러주어야 합니다.

---

2. 소스코드

 

[Github 링크 : (클릭)]

#include <bits/stdc++.h>
using namespace std;

const int INF = 2147000000;
int n, cache[100001];

int GetAnswer(int k)
{
	int &ret = cache[k];
	if(ret != -1) return ret;
	if(k==0 || k==2 || k==5) return ret = (k ? 1 : 0);

	ret = INF;
	if(k-2 >= 0) ret = GetAnswer(k-2) + 1;
	if(k-5 >= 5) ret = min(ret, GetAnswer(k-5) + 1);
	
	return ret;
}

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

	cin>>n; 

	memset(cache, -1, sizeof(cache));
	int ans = GetAnswer(n);
	cout<<(ans >= INF ? -1 : ans)<<'\n';

	return 0;
}