[백준] 11047 - 동전 0

#include <iostream>
using namespace std;

int num;
int main() {
	int n, k;
	int coin[11];
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> coin[i];
	}
	for (int i = n; i > 0; i--)
	{
		num += k / coin[i];
		k %= coin[i];
	}
	cout << num;
}

풀이: 입력은 작은 순서대로 저장되기 때문에 정렬은 할 필요가 없다. 두 번째 for문에서 num 변수에 몇 개의 코인을 사용했는지 개수를 저장하고 k 변수에 사용된 코인을 제외한 남은 잔돈을 저장하였습니다. 이 문제에서 그리디 알고리즘이 적용이 가능한 이유는 큰 동전이 그 동전 보다 하나 작은 동전에 배수이기 때문에 그리디 알고리즘으로 풀 수 있습니다. 

가장 효율적인 방법이 단순히 큰 동전부터 사용하는 것이기 때문에 (배수 관계일 때) 그리디를 사용했습니다.