알고리즘 문제풀이
[백준/BOJ] 백준 5585번 : 거스름돈
GeniusJo
2020. 6. 9. 00:42
https://www.acmicpc.net/problem/5585
5585번: 거스름돈
문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건�
www.acmicpc.net
그리디 알고리즘을 통해 문제를 해결하였다.
잔돈을 가장 적게 주려면, 가능한 금액이 큰 동전을 돌려줘야 한다. 이 코드에서는 point변수를 이용해 남은 잔돈에 대해 가능한 큰 금액의 동전을 구하였다.
코드
#include <iostream>
#include <vector>
using namespace std;
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
vector<int> coin;
int pay;
int result;
int point = 0;
int cnt = 0;
//동전을 내림차순으로 정리한다.
coin.push_back(500);
coin.push_back(100);
coin.push_back(50);
coin.push_back(10);
coin.push_back(5);
coin.push_back(1);
cin >> pay;
result = 1000 - pay;
//더이상 잔돈이 없을때 종료
while (result != 0)
{
//잔돈이 point지점의 동전보다 작다면 더 작은 동전 선택을 위해
//point지점을 한칸 옮긴다
if (result < coin[point] && (point+1 < 6) )
point++;
else
{
result -= coin[point];
cnt++; //개수 추가
}
}
cout << cnt;
return 0;
}