[백준 BOJ][C++]11047번 동전 0 풀이: 그리디 알고리즘

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

11047번: 동전 0

 

 입력으로 주어지는 동전의 가치 Ai가 오름차순으로 주어졌음으로 제일 가치가 큰 동전부터 비교해가며 풀이를 진행하면 됩니다. 

 

 가치 k를 만들기 위해 필요한 동전의 수가 최소가 되기 위해선, 먼저 k보단 작은 수들 중에서 가장 큰 수를 뽑아 k를 나눈 몫이 그 동전의 개수를 의미합니다. 

 그 나머지는 남은 가치의 합을 나타내고 위 과정을 나머지가 0이 될때까지 반복하면 됩니다. 

 

#include<iostream>

using namespace std;

int main(void) {

	int n, k;
	int value[11];
	int ans = 0;

	cin >> n >> k;

	for (int i = 0; i < n; i++)
		cin >> value[i];

	for (int i = n - 1; i >= 0; i--) {
		if (k == 0)
			break;

		if (k < value[i])
			continue;

		ans += (k / value[i]);
		k %= value[i];
	}

	cout << ans;

	return 0;
}