(C++) 백준 11047번 - 동전 0

문제 링크 : https://www.acmicpc.net/problem/11047

11047번: 동전 0

문제 풀이

그리디 알고리즘을 활용한 문제이다.

가장 동전 수를 적게 이용하려면 금액이 큰 동전부터 빼가면서 계산해야 한다.

금액이 오름차순으로 입력되기 때문에 배열의 뒷부분부터 계산해 나가는 식으로 풀이하였다.

#include <iostream>

using namespace std;

int coins[12];
int n, k, cnt;

int main() {
    ios::sync_with_stdio(0);  
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> k;

    for(int i = 0; i < n; i++) cin >> coins[i];
    for(int i = n-1; i >= 0; i--){
        if(coins[i] > k) continue;
        int num = k / coins[i];
        k -= num * coins[i];
        cnt += num;
    }
    cout << cnt;
}