[백준/C++] 11047 동전0 (S4)

유형	난이도	완료일	링크	특이사항
그리디	실버4	23/03/15	https://www.acmicpc.net/problem/11047

 

 

내 코드

#include <iostream>
#include <algorithm>

using namespace std;

int coin[10];

int main(void)
{
	int n,k;
	cin >> n >> k;
	
	for(int i=0; i<n; i++)
	{
		cin >> coin[i];
	}
	
	int remnant = k;
	int used = 0;
	
	for(int i=n-1; i>=0; i--)
	{
		if(remnant==0)
		{
			cout << used;
			return 0;
		}
		
		if(remnant < coin[i])
		{
			continue;
		}
		else
		{
			used += remnant/coin[i];
			remnant -= coin[i]*(remnant/coin[i]);
		}
	}
	
	cout <<used;
}

 ‘동전 1’ 문제를 풀다가 막혀서 이 문제를 발견하고 풀어보았다. 동전의 개수가 10개로 매우 작고, 각 동전의 가치가 모두 이전 동전의 배수로 주어진다는 것이 특징이었다. 이 조건 덕분에 무조건 들어갈 수 있는 가장 큰 가치의 동전을 최대로 사용하는, 그리디 적인 방식으로 바로 해결할 수 있었다.

이름은 같은 동전이긴 하지만 동전 1 문제에는 전혀 사용할 수 없는 풀이인 것 같다. n번째 동전이 n-1번째 동전의 배수라는 조건이 없다면 결국 “최대 가치를 가진 동전을 최대로 사용하기” 전략이 최적 해를 보장하지 않기 때문이다.