동전 0 11047

문제

접근 방법

큰 값부터 사용해 주는 것이 가장 적은 동전을 사용하는 방법일 것이다.
동전의 값으로 나눈 값이 사용한 동전의 개수이다.
나머지는 동전의 값으로 해결하고 남은 가치이다.

코드

#include <iostream>
using namespace std;
int A[10], N, K, ret = 0;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> K;
    for (int i = 0; i < N; ++i)
        cin >> A[i];
    for (int i = N - 1; i >= 0; --i)
    {
        int div = K / A[i];
        if (!div)
            continue;
        ret += div;
        K %= A[i];
    }
    cout << ret;
    return 0;
}

풀이

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

위의 조건 덕분에 불가능한 경우는 존재하지 않고 무조건 큰 값부터 사용하는 것이 이득이 된 것이다. (배수라는 것은 이전 값을 포함한다는 뜻이므로)