[백준]동전 0

백준저지

[동전 0]https://www.acmicpc.net/problem/11047

• 그리디 알고리즘을 요구하는 문제

• 핵심은 큰 금액부터 작은 금액으로 내려가면서 동전의 개수를 구해야 한다.

• 푸는데 걸린 시간은 약 10분 정도 걸렸다.

#include <iostream>
using namespace std;
int val[11];
int main(void) {
	int N, K, ans = 0, sum = 0;
	cin >> N >> K;
	
	for (int i = 1; i <= N; i++)
		cin >> val[i];

	for (int i = N; i >= 1; i--) {
		if (val[i] < K) {
			while (sum <= K) {
				sum += val[i];
				ans++;
			}  sum -= val[i]; ans--;
		}
	}
	cout << ans;
	
	return 0;
}