[백준] 11047 C++ 동전0 (그리디 알고리즘)

- 문제 설명

 

 

- 문제 풀이

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

그리디 알고리즘(greedy algorithm)이란 탐욕 알고리즘이라고도 불리는데 그리디 알고리즘의 모토는

"지금 당장 최적인 답" 을 이용하자는 것이다.

단 이 알고리즘은 지금 당장에 대해선 최적이지만 전체를 봤을 때 최적이라는 보장이 없다는게 특징이다.

 

이번 문제와 같은 거스름돈 문제는 무조건 최대한 가치가 높은 동전부터 나눠야하므로 그리디 알고리즘에 적합하다.

심지어 정렬이 된 상태로 주어지므로 역순으로 값이 나눠지는지를 보며 검사하기만 하면 된다.

 

 

- 코드

#include <iostream>
using namespace std;

int N, K, result = 0;
int cnt[10];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> K;
	for (int i = 0; i < N; i++)
		cin >> cnt[i];

	for (int i = N - 1; i >= 0; i--)
	{
		if (K / cnt[i] >= 1)
		{
			result += K / cnt[i];
			K = K % cnt[i];
		}
	}

	cout << result;

	return 0;
}