백준 - 동전 0 : 11047번

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

11047번: 동전 0

이번 문제의 조건 중에 가장 중요한 부분은 아래 내용이다.

아래 조건이 있기 때문에 그리디 알고리즘이 적용가능하다.

 

i ≥ 2인 경우에 Ai는 Ai-1의 배수

 

#include <bits/stdc++.h>
using namespace std;

int main(void)
{
    int n, k;
    int in[10];

    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> in[i];
    }

    int cnt = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        while (k / in[i])
        {
            cnt += k / in[i];
            k = k % in[i];
        }
    }

    printf("%d", cnt);

    return 0;
}