[백준 BOJ / C++] 5585번: 거스름돈 풀이

문제

 

<문제>

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한 장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 

예를 들어 입력된 예 1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다.

 

<입력>

입력은 한줄로 이루어져 있고, 타로가 지불할 돈(1 이상 1000 미만의 정수) 1개가 쓰여있다.

 

<출력>

제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.

 

 

www.acmicpc.net/problem/5585

5585번: 거스름돈

 

 

 

문제 풀이

 

Greedy(탐욕 법) 알고리즘을 이용해 문제를 해결합니다. 잔돈의 액수가 큰 동전부터 최대한 많이 거슬러준다고 생각하면 최소 동전의 개수를 구할 수 있습니다. 

 

change에 거스름돈을 저장하고, 500엔, 100엔 50엔, 10엔, 5엔 순서대로 거슬러줄 수 있는 동전의 개수를 구하여 answer에 더합니다. 거슬러준 뒤의 change를 다시 계산한 뒤(나머지 연산) 다음 동전에 대한 계산을 진행합니다. 1엔은 단순히 남은 change를 더해주었습니다. 

 

 

 

 

소스코드

 

// 5585번: 거스름돈
#include <iostream>
 
using namespace std;
 
int main() {1
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int change, answer = 0;
    cin >> change;
    change = 1000 - change;
    
    answer += change / 500;
    change %= 500;
 
    answer += change / 100;
    change %= 100;
 
    answer += change / 50;
    change %= 50;
 
    answer += change / 10;
    change %= 10;
 
    answer += change / 5;
    change %= 5;
 
    answer += change;
 
    cout << answer << "\n";
 
    return 0;
}

 

 

 

 

 

 

공부한 것을 정리한 내용입니다. 수정할 부분이 있다면 알려주시면 감사하겠습니다 :)