[C++] 백준 BOJ 11047 동전 0

문제링크 : https://noj.am/11047

최소의 동전 갯수로 주어진 금액을 때려맞추는 그리디한 문제이다.

주어진 동전도 이미 정렬되어있기 때문에 솔루션도 매우 간단하다.

큰 동전부터 차례대로 나누어서 값을 누적시키고 나머지 값들은 더 작은 단위의 동전으로 나눠서 또  누적시키면 쉽게 구할  수 있다.

혹시라도 중간에 모든 동전을 소진했을 경우 바로 탈출하기  위해 24번째 줄과 같이 total == 0일 경우 탈출하는 조건을  두었다.

// BOJ_11047 동전 0
#include <iostream>
 
using namespace std;
 
int coins[11];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int N, total;
    cin >> N >> total;
 
    for(int i = 0; i < N; i++)
        cin >> coins[i];
 
    int result = 0;
 
    for(int i = 1; i <= N; i++){
        result += total / coins[N-i];
        total %= coins[N-i];
        if(total == 0)
            break;
    }
    cout << result;
 
    return 0;
}