동전0 - 11047번

해결방법

알고리즘은 그리디를 사용하였다. 하지만 그리디를 사용해도 최적인지 증명과정이 필요하다.

증명

문제에서는 i개의 동전이 있고, 오름차순으로 주어진다. N을 금액이라고 할 때 동전이 N보다 작다면 항상 아래와 같다.
$$ N / C_{i} <= N / C_{i-1} $$
N에 동전금액 만큼 제거 값을 N2라고 하자. 동전이 N2보다 작다면 똑같은 결과가 나온다.
$$ N2 / C_{i} <= N2 / C_{i-1} $$
따라서 항상 제일 큰 코인으로 세는 것이 가장 작다.

전체코드

#include<iostream>
using namespace std;
int c[10], K, N;
int main() {
    cin >> K >> N;
    int ans = 0;
    for (int i = 0; i < K; ++i)
        cin >> c[i];
    for (int i = K - 1; i >= 0; --i)
        if (N >= c[i]) {
            ans += N / c[i];
            N -= (N / c[i] * c[i]);
        }
    cout << ans << endl;
    return 0;
}