알고리즘/BOJ
백준 5585번: 거스름돈
대 혁
2020. 7. 26. 01:59
5585번: 거스름돈
문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건�
www.acmicpc.net
https://onlytrying.tistory.com/124 동전 0 문제와 같은 유형의 문제였다.
엔화가 1, 5, 10, 50, 100, 500 단위인 것을 보면 배수로 이루어져 있다는 것을 알 수 있다.
따라서 가장 큰 금액인 500엔부터 비교하도록 구현하면 된다.
#include <iostream>
using namespace std;
int money[6] = { 500, 100, 50, 10, 5, 1 };
int Greedy(int change)
{
int cnt = 0;
for (int i = 0; i < 6; i++)
if (change >= money[i])
{
cnt += change / money[i];
change %= money[i];
}
return cnt;
}
int main(void)
{
int price;
cin >> price;
cout << Greedy(1000 - price) << endl;
}
알고리즘 200일 프로젝트 - 110 day