BAEKJOON/greedy
[baekJoon5585] 거스름돈
ferozsun
2020. 8. 5. 10:10
https://www.acmicpc.net/problem/5585
5585번: 거스름돈
문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건�
www.acmicpc.net
IDEA: Greedy Algorithm
거스름돈을 가장 큰 가치의 동전부터 최대한 많은 개수가 되도록 계산
/*
날짜: 2020.08.05
번호: 5585
문제: 거스름돈의 최소 동전 수
*/
#include <iostream>
#include <vector>
using namespace std;
int main() {
int cost; cin >> cost; // 물건 가격
int change = 1000 - cost; // 거스름돈
vector<int>coin = { 500, 100, 50, 10, 5, 1 };
int num = 0;
for (int i = 0; i < 6; ++i) {
while (change >= coin[i]) {
change -= coin[i];
num++;
}
}
cout << num << "\n";
}