[BOJ/백준 5585][C++] 거스름돈

문제

https://www.acmicpc.net/problem/5585

백준 5585

 

문제 내용

물건을 사고 1000엔 지폐를 낸다.

잔돈은 500엔, 100엔, 50엔, 5엔, 1엔이 준비되어있다.

거스름돈을 최소 개수로 받는다고 할 때, 잔돈의 개수를 구하면 된다.

 

문제 풀이

잔돈이 서로 배수관계에 있으므로 greedy 문제이다.

잔돈이 큰 것부터 먼저 계산하면 된다.

 

코드

#include <iostream>
using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int num,result=0;
	cin >> num;
	num = 1000 - num;
	
    	//문제 해결
	result += num / 500;
	num %= 500;

	result += num / 100;
	num %= 100;

	result += num / 50;
	num %= 50;

	result += num / 10;
	num %= 10;

	result += num / 5;
	num %= 5;

	result += num;
	
    	//결과 출력
	cout << result << '\n';
}