[백준] 알고리즘 14916번 - 거스름돈 문제

문제

www.acmicpc.net/problem/14916

14916번: 거스름돈

소스코드

#include <bits/stdc++.h>
using namespace std;
int dp[100001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	dp[1]=50001,dp[2] = 1,dp[3]=50001,dp[4]=2, dp[5] = 1;
	for (int i = 6; i <= n; i++) {
		dp[i] = min(dp[i - 2] + 1, dp[i - 5] + 1);
	}
	if (dp[n]>50000) cout << -1;
	else cout << dp[n];
}

풀이

2,5의 숫자만으로 이루어진 거스름돈을 정확하게 분배해줘야 한다.

우선 5까지 초기값을 설정해준다.

2,5로 거슬러 줄 수 없는 동전에는 값이 큰 값을 저장해준다.

즉 둘다 거슬러 주지 못할때는 5만이상의 값이 저장되고

2 또는 5로 거슬러질때는 둘의 최소값을 저장하여 출력한다.