[백준 14916] - 거스름돈(c++)

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

dp 문제이고,

입력된 n값에 대해 2원, 5원으로 거슬러 줄 때 최소의 동전개수를 사용하는 문제입니다.

메모이제이션을 활용하여 단계별로 값을 배열에 저장해 계산해 줍니다.

 

문제 분석

먼저 배열 간 값들의 관계를 도출하기 위해 (점화식) 값을 직접 계산해 봅니다.

구성할 수 없는 경우는 -1로 작성하였습니다.

n	최소 동전 개수
1	-1
2	1
3	-1
4	2
5	1
6	3
7	2
8	4

이제 값들 간 관계를 구해봅시다. 점화식은 대충 a(n) 이라 놓고

n이 4인 경우에 최소 동전 개수는 2원짜리 동전 하나씩을 사용하니 1 + 1 = 2 로 계산했습니다.

이 경우 a(4) = a(2) + a(2) 라고 할 수 있습니다.

n이 7인 경우는 a(7) = a(5) + a(2) 로 계산될 수 있습니다.

그런데 n= 10 인 경우 같은 경우에는 거슬러 줄수 있는 경우의 수가 아래와 같이 2가지 입니다.

1. 2 + 2 + 2 + 2 + 2
2. 5 + 5

이런 경우 사용된 동전의 최소값(2) 를 배열에 넣어야겠죠.

따라서 a(n-2) + a(2)와 a(n-5) + a(5) 중 최소값을 구해서 배열에 넣어줍니다.

소스 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;
int dp[100001];

int findval(int n)
{
	if (dp[n]!= 0)
	{
		return dp[n];
	}
	else
	{
		int tmp1 = findval(n - 2) + dp[2];
		int tmp2 = findval(n - 5) + dp[5];
		if (tmp1 >0 && tmp2 > 0)
		{
			dp[n] = min(tmp1, tmp2);
		}
		else if (tmp1 > 0)
		{
			dp[n] = tmp1;
		}
		else
		{
			dp[n] = tmp2;
		}
		return dp[n];
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	dp[0] = -1;
	dp[1] = -1;
	dp[2] = 1;
	dp[3] = -1;
	dp[4] = 2;
	dp[5] = 1;

	cout << findval(n);
}