5주차 - 그리디 알고리즘 (백준 11047)

백준 11047번

그리디 알고리즘을 통해 해결할 수 있는 간단한 문제이다.
특히 동전의 단위가 배수이므로, 큰 단위의 동전부터 나눠주고, 차례로 진행하면 된다.

#include<iostream> 
using namespace std; 

int main() { 
    int n, k; 
    int sum = 0; 
    int a[11]; 
    cin >> n >> k; 

    for (int i = 0; i < n; i++)
       cin >> a[i]; 
   
    for (int i = n - 1; i >= 0; i--) {
       sum += k / a[i]; 
       k = k % a[i];
    }
    cout << sum << endl;
    return 0;
}