[백준] 5585번 거스름돈

 

 

문제

소스코드

#include<iostream>
 
int main() {
    int money{};
    std::cin >> money;
    int change[6] = { 500,100,50,10,5,1 };
    int result{};
 
    //구매금액에서 빼기
    money = 1000 - money;
 
    for (int i = 0; i < 6; ++i) {
 
        //몫이 0이라면 나눌 수 없는 수
        if (money / change[i] == 0)
            continue;
 
        result+=(money / change[i]);
        money %= change[i];
    }
    std::cout << result << "\n";
 
}

 

후기

이 문제를 해결하기 위한 키워드는 그리디(Greedy)이다.

그리디 탐욕 알고리즘은 최적화 문제를 해결하는 데 사용할 수 있는 가장 간단하며 쉽게 구현할 수 있는 알고리즘이다.

거스름돈 거슬러주기 와 최소비용 신장트리 가 대표적인 탐욕 알고리즘을 적용할 수 있는 문제이다.

 

해당 금액을 전부 배열에 넣은 후 반복문을 돌면서 값을 나누게 했으며 몫이 0이라면 나눌 수 없는 수 이기 때문에 넘어가고 그 외에는 그 몫만큼 더한 다음 출력하게 하였다.

 

 

출처 및 레퍼런스

문제 링크: www.acmicpc.net/problem/5585