[Codeup] 2634. 거스름돈 II

 

 

1. 문제 링크

https://codeup.kr/problem.php?id=2634

코드업

 

2. 문제 풀이

1) Greedy의 문제점

최소의 동전의 수를 출력해야 한다. 가장 먼저 생각하게 되는 것은 가장 큰 동전으로 거슬러 주는 방법이다.

문제의 입력 예시도 가장 큰 동전부터 차례대로 거슬러 주면 최소의 동전 수를 출력하고 있다. (악질이다.)

 

이 문제는 매 순간 최선의 선택. 즉, Greedy하게 주면 반례가 생긴다.

거스름 돈 : 6원
동전 종류 : 3개
동전 : 1원, 3원, 4원

 

위와 같다고 하면, 최선의 선택을 하면 4원을 먼저 주기 때문에 동전의 수는 3개(4원 + 1원 + 1원)가 된다.

※ 즉, 거스름 돈 문제에서 그리디가 가능한 것은 동전 간 배수 관계가 보장될 때 해당한다.

 

2) 다른 방법

현재 만들 수 있는 금액에서 동전 하나를 추가하면 더 큰 금액을 만들 수 있다.

가장 작은 금액부터 시작해서, 만들 수 있는 금액들을 차례대로 확장해 나간다.

 

이 과정에서 어떤 금액을 만드는 방법이 여러가지 있을 수 있다.

따라서, 항상 동전 개수가 더 적은 방법을 선택하도록 갱신해 나간다.

 

모든 가능한 금액을 확장해 나가면, 목표 금액을 만들 때 필요한 최소 동전 개수를 구하는 것이 가능하다.

 

3. 아이디어

1. dp[x]를 x원을 만드는 최소 동전 개수라고 정의한다.
2. 이때, 초기 상태로 dp[0] = 0, 나머지의 초기 값은 동전의 최대 값보다 크게 잡는다.
3. 현재 만들 수 있는 금액 n에 대해 각 동전 coin을 하나씩 사용해 n + coin을 만든다.
4. 이때, 기존 값보다 더 적은 경우에만 갱신한다. 이 과정을 통해 모든 금액에 대한 최소 동전 개수를 구할 수 있다.

 

4. 구현

※ C++ Source Code

#include <iostream>
#include <algorithm>
using namespace std;
int dp[10005];
int money;
int coin_count;
int coin[15];
int main(void)
{
	cin >> money;
	cin >> coin_count;

	fill_n(dp, 10005, 10005);
	dp[0] = 0;
	for (int i = 0; i < coin_count; i++)
	{
		cin >> coin[i];
	}

	for (int i = 0; i <= money; i++)
	{
		for (int j = 0; j < coin_count; j++)
		{
			if (i + coin[j] > money || dp[i] == 10005) continue; // money 넘어가는 값은 범위 밖. dp[i]가 아직 10005이면 해당 값으로는 계산해도 의미없음.(아직 만들 수 없는 수라는 뜻)
			dp[i + coin[j]] = min(dp[i + coin[j]], dp[i] + 1); // dp[i]에서 코인 하나를 더해서 만들 수 있는 값과 기존 저장되어있는 값 중 더 작은 값이 최소값이됨. 
		}
	}
	cout << dp[money];
}