알고리즘/코테 문제
[BOJ/백준 5585][C++] 거스름돈
gyong
2022. 4. 21. 19:50
반응형
문제
https://www.acmicpc.net/problem/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';
}
반응형