[11047] 동전 0

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

11047번: 동전 0

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

코드

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <vector>

using namespace std; 

int N, K;
vector<int> A;
int ans = 0;

int main(void){
	cin >> N >> K;
	for(int i=0; i<N; ++i){
		int a;
		cin >> a;
		A.push_back(a);
	}

	int maxx = A[N-1];

	while(K != 0){
		for(int i=0; i<N; ++i){
			if(K/A[i] ==0){
				maxx = A[i-1];
				break;
			}
		}

		ans += K/maxx;
		K -= (K/maxx) * maxx;
	}

	cout << ans;

	
	return 0;
}

그리디 알고리즘의 가장 대표적인 문제이다. 

그리디 알고리즘을 간단하게 설명해 보자면 말그대로 탐욕적인 알고리즘으로 '현재'의 기준에서 어떻게 하면 가장 최적화된 답을 도출할 수 있을까에 대한 답을 내놓는 알고리즘이다.

예를 들어 현재 문제인 동전0는 동전 개수의 최소값을 구하는 문제인데 이 최소값을 구하려면은 가장 큰 종류의 동전을 먼저 소비하고 뒤에는 내림차순대로 동전을 소모해 K원을 만들면 동전 개수가 가장 최소값이 나오게 된다.

말 그대로 먼저 소비할 수 있는 가장 큰 동전을 소비해나가면 최소값을 찾을 수 있는데 이와 같이 앞의 선택이 이후의 선택에 영향을 주지 않는다면 그리디 알고리즘을 활용할 수 있다.