백준 C++ | #17 BOJ5585 거스름돈 C++ 문제 풀이

Computer Science/C++

백준 C++ | #17 BOJ5585 거스름돈 C++ 문제 풀이

토마토. 2022. 8. 16. 16:09

5585번: 거스름돈

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사

www.acmicpc.net

#include <iostream>
using namespace std;

int main() {
	int money;
	cin>>money;
	int remain=1000-money;
	int count=0;
	count=remain/500+(remain%500)/100+(remain%100)/50+(remain%50)/10+(remain%10)/5+(remain%5)/1;
	cout<<count;
}

이렇게 500부터 하나씩 그 당시의 최선으로 적으면 그게 그리디 알고리즘인가보다.

#include <iostream>

int main() {
	int left;
	std::cin >> left;
	left = 1000 - left;

	int count = 0, tmp=0;
	tmp = left / 500;
	count += tmp;
	left -= 500 * tmp;

	tmp = left / 100;
	count += tmp;
	left -= 100 * tmp;

	tmp = left / 50;
	count += tmp;
	left -= 50 * tmp;

	tmp = left / 10;
	count += tmp;
	left -= 10 * tmp;

	tmp = left / 5;
	count += tmp;
	left -= 5 * tmp;

	tmp = left;
	count += tmp;
	left -=tmp;

	std::cout << count << std::endl;

	return 0;
}