백준 11047 동전 0

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

 

서론

그리디 알고리즘 문제.

동전들이 배수관계여서 그리디 알고리즘의 결과가 최적해를 가지는것같다.

 

---

아이디어

k값에 더할 수 있는 동전 중 가장 큰값을 반복해서 더해준다. 더해줄때마다 횟수를 체크해서 출력한다.

예제 k=4200에서

4200 = 1000 + 1000 + 1000 + 1000 + 100 + 100

 

---

구현

//c++

#include <iostream>

using namespace std;

int coin[10];

int main() {
	int n, k;
	cin >> n >> k;
	for (int i = n-1; i >= 0; i--) cin >> coin[i];

	int sum = 0;
	int cnt = 0;
	while (sum != k) {
		for (int i = 0; i < n; i++) {
			if (k - sum >= coin[i]) {
				sum += coin[i];
				cnt++;
				break;
			}
		}
	}
	cout << cnt;
}