풀이

i번 동전의 가치는 (i-1)번 동전의 가치의 배수이므로, 큰 가치의 동전을 최대한으로 거슬러주면, 최소 개수의 동전을 사용한다는 걸 보장할 수 있다.

코드

#include <iostream>
using namespace std;

int N, K;
int A[10];
int answer;

int main()
{
    cin >> N >> K;
    for (int n = 0; n < N; n++) {
        cin >> A[n];
    }
    
    // 큰 수부터 내려오면서 최대한 큰 수로 거슬러준다.
    for (int i = N - 1; 0 <= i; i--) {
        answer += K / A[i]; // A[i]원으로 거슬러주는 개수를 answer에 더함.
        K = K % A[i];
    }
    cout << answer << '\n';
    return 0;
}
}

결과