[백준 11047] 동전 0

문제
동전을 적절히 사용해서 가치의 합을 K로 만들려고 한다.
이때 필요한 동전 개수의 최솟값을 구하라.

입력
첫째 줄에 N과 K
N은 1이상 10이하
K는 1이상 일억이하
둘째 줄부터 N개의 줄에 동전의 가치 A가 오름차순으로 주어진다.

출력
K원을 만드는데 필요한 동전 개수의 최솟값 출력

---

직관적으로 화폐가치가 높은 것으로 채워야 동전의 개수가 최소가 된다.

따라서 입력받은 N개의 동전을 내림차순으로 정렬하여 하나씩 꺼내어 나눠본다.

나누었을 때 1이상이면 나눈 몫을 최종해에 더하고 (몫x화폐가치)만큼 K원에서 빼준다.

K가 0원이 되었을 때 반복문을 종료하도록 한다.

 

#include "pch.h"
#include <iostream>
#include<algorithm>
#include <vector>
using namespace std;


int main()
{
	int N, K;
	int coin[10];

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

	sort(coin, coin + N, greater<int>());

	int answer = 0;
	int idx = 0;
	while (K != 0) {
		if (K / coin[idx] > 0) {
			int cnt = K / coin[idx];
			answer += cnt;;
			K -= (coin[idx] * cnt);
		}
		idx += 1;
	}

	cout << answer << endl;
	return 0;
}