[BaekJoon][Greedy] 11047. 동전 0

/* 문제 : [11047] 동전 0
[input]
10 4200
1
5
10
50
100
500
1000
5000
10000
50000
[output]
6
[설명]
첫째 줄에 동전의 종류 N과 K원이 주어진다.
둘째 줄부터 동전의 가치가 오름차순으로 주어진다.
이 때, K원을 만드는데 필요한 동전 개수의 최소값 출력해라
*/
#include <iostream>
#include <list>

using namespace std;

int main()
{
	list<int> coinList; // 동전의 가치를 저장할 리스트 
	int n, k;			// 동전의 종류, 만들어야 될 K원
	int count = 0;		// 필요한 동전의 개수

	cin >> n >> k;
	
	for (int i = 0, s; i < n; i++) {
		cin >> s;
		coinList.push_back(s);
	}

	coinList.reverse(); // 큰 것부터 나누기 위해 오름차순 정렬
	list<int>::iterator iter = coinList.begin();

	while (iter != coinList.end()) {
		if (k >= *iter) {
			count += k / *iter;
			k %= *iter;
		}
		
		iter++;
	}

	cout << count;
	return 0;
}