[백준] 알고리즘 5585번 - 거스름돈 문제

거스름돈 문제

www.acmicpc.net/problem/5585

5585번: 거스름돈

소스코드

#include <bits/stdc++.h>
using namespace std;
int coin[6] = { 500,100,50,10,5,1 };
int main(){
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   int n, ans=0;
   cin >> n;
   n = 1000 - n;
   for (int i = 0; i < 6; i++) {
       int temp = n / coin[i];
       if (temp) {
           ans += temp;
           n %= coin[i];
       }
   }
   cout << ans;
}

해결방법

타로가 지불한 돈은 1000엔인고 물건의 가격은 n으로 주어집니다.

최소한의 거스름돈의 개수를 원하니 그리디 알고리즘으로 생각합니다.

먼저 가장 큰 순서의 거스름돈으로 거슬러 준다고 생각하면 됩니다.