BOJ 11047 - 동전 0 [C/C++] / Greedy Algorithm

11047번: 동전 0 (acmicpc.net)

11047번: 동전 0

문제 설명은 다음과 같다.

문제 설명 / 입력 / 출력

예제 입력 / 예제 출력

앞서 포스팅한 ATM 문제와 매우 비슷한 문제라고 할 수 있다.

 

주어진 값을 최소 개수의 동전을 사용해서 표현하려면 어떻게 해야할까?

 

당연히 한 개당 금액이 높은 동전을 최대한 많이 사용해야 할 것이다.

 

때문에, 금액이 큰 동전부터 내려가면서 표현할 수 있는 동전을 구해주면서 내려간다.

 

아래는 제출한 C/C++ 코드이다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>

using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    string s;
    getline(cin, s);
    istringstream ss(s);
    int n;
    int total;
    ss >> n >> total;
    vector<int> coins;
    for (int i=0;i<n;i++) {
        int coin;
        cin >> coin;
        coins.push_back(coin);
    }
    int cnt = 0;
    while (total>0){
        if (total/coins.back()==0) coins.pop_back();
        else {
            cnt += total/coins.back();
            total -= (total/coins.back())*coins.back();
            coins.pop_back();
        }
    }
    cout << cnt;
    return 0;
}

벡터 자료구조를 사용해서, Coin 한 개당 금액들을 밀어넣었다.

 

이제 하나씩 pop_back() 해 나가면서, 남은 total 금액이 그 동전의 금액으로 표현될 수 있다면 표현하고, 표현된 금액만큼 마이너스 하면서 반복한다.

 

표현한 동전의 개수만큼 cnt에 더해주고, 마지막엔 cnt를 출력해 준다.

 

Terminate 조건은 total이 다 빼져서 0보다 작거나 같아질 때이다.