[백준] 11047 – 동전 0

by

쉬운 목차

문제

#11047: 코인 0 (acmicpc.net)

11047호: 코인 0

'추천 관련글,

N과 K는 첫 번째 줄에 표시됩니다.

(1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 두 번째 행부터 오름차순으로 N행에 주화의 값 Ai를 부여한다.

(만약 1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2, Ai는 Ai-1의 배수)

www.acmicpc.net

설명

필요한 최소 동전 수를 찾으려면 가장 큰 액면가 동전부터 시작하십시오.

그리고 동전의 단위는 곱셈비로 주어지기 때문에 즉시 계산할 수 있습니다.

N-1에서 루프를 시작하는 이유는 동전 단위가 오름차순으로 주어지기 때문에 배열의 끝에서 시작해야 합니다.

#include <iostream>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    
    int coin(10);
    for (int i = 0; i < N; i++) {
        cin >> coin(i);
    }
    
    int amount = 0;
    for (int i = N-1; i >= 0; i--) {
        amount += K / coin(i);
        K = K % coin(i);
    }
    
    cout << amount;

    return 0;
}