그리디 알고리즘_거스름 돈

그리디(Greedy) 알고리즘

당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘

장점

항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있음
-> '특정한 상황'에 있어서는 최적의 해를 보장함

거스름 돈 문제

1260원을 500원, 100원, 50원, 10원을 이용하여 최소 개수의 동전으로 필요한 거스름 돈 만들기
1260 / 500 = 2
260 / 100 = 2
60 / 50 = 1
10 / 10 = 1
총 6개의 동전이 필요

#include <iostream>

int MakeChange(int Money)
{
	const array<int, 6> Coins = { 500, 100, 50, 10 };
    int CoinNum = 0;
    
    for(int Coin : Coins)
    {
    	CoinNum += Money / Coin;
        Money %= Coin;
    }
    
    return CoinNum;
}

이전에 풀었던 [백준] 11047: 동전 0 문제를 위 방식을 적용하여 다시 풀어 보기

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

using namespace std;

int MakeChange(int Money, const vector<int>& Coins)
{
    int CoinCount = 0;

    for (int Coin : Coins)
    {
        CoinCount += Money / Coin;
        Money %= Coin;
    }

    return CoinCount;
}

int main()
{
    int N, K = 0;
    cin >> N;
    cin >> K;
    vector<int> Coins;

    for (int i = 0; i < N; i++)
    {
        int Coin = 0;
        cin >> Coin;
        Coins.push_back(Coin);
    }

    sort(Coins.begin(), Coins.end(), greater<int>());

    cout << MakeChange(K, Coins);
}

이전 제출과 결과 비교

🌱 메모리와 시간 모두 단축됨