[Baekjoon] 11047번: 동전 0

🥅 문제

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

 

🔍 설계

K를 달성시키는 동전의 최소 개수를 구해야 하는데, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수라는 조건이 있으므로, 가치가 큰 동전부터 최대한 사용하는 그리디 문제라는 것을 파악할 수 있다.

 

👊 풀이

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int n, k, result = 0;
vector<int> coins(10);

int main() {
	cin >> n >> k;
	for (int i=0; i<n; i++){
		cin >> coins[i];
	}
	for (int i=n-1; i>=0; i--){
		result += k / coins[i];
		k %= coins[i];
	}
	cout << result << "\n";
	return 0;
}