그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘 

결정해야 할 때, 그 순간에 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘

그 때 그 때는 최적일수도 있지만 최종적으로는 최적의 해가 아닐 수도 있다.

 

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

11047번: 동전 0

 

 

소스 코드

#include <iostream>
using namespace std;
int coin[10];

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

큰 동전부터 살펴보고 배수관계라면 개수만큼 빼준다.