알고리즘/백준
[백준/C,C++] 5585번: 거스름돈
이민훈
2021. 4. 20. 07:02
5585번: 거스름돈
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사
www.acmicpc.net
풀이
그리디 알고리즘 문제 중에서 가장 기초적인 문제입니다.
현재 받을 수 있는 화폐의 종류 중 값이 큰 것부터 잔돈에서 빼주면 됩니다.
#include<iostream>
using namespace std;
int main(void)
{
int n; cin >> n;
n = 1000 - n;
int changes[6] = { 500, 100, 50, 10, 5, 1 };
int res = 0;
for (int i = 0; i < 6; i++) {
int tmp = n / changes[i];
n -= (tmp * changes[i]);
res += tmp;
if (n == 0) break;
}
cout << res;
return 0;
}반례
Input
10
Output
10
Input
520
Output
8
Input
1000
Output
0