[탐욕법] 거스름돈(난이도:하)

1. 문제정의

 최근 개인 사업을 시작한 광성이는 매일 아침마다 은행에 가서 동전과 지폐들을 교환해 오는 것이 일이다. 현금으로 물건 값을 지불할 경우 조금 더 싸게 한 덕분에 현금으로 구입하는 사람이 많은데, 대부분의 손님들이 물건 값보다는 더 많은 돈을 내서 꼭 거스름돈이 필요해지는 일이 발생하기 때문이다.

 그래서 최대한 적은 지폐랑 동전을 사용하여 거스름돈을 주고 싶은데, 광성이를 위해서 물건값과 받은 금액이 주어졌을 때, 거스름돈으로 지불할 지폐 혹은 동전의 최소 개수를 출력하는 프로그램을 작성하시오.

 

입력

첫줄에는 테스트 케이스 수

둘째 줄부터 T + 1번째 줄까지는 물건의 값과 받은 금액이 주어진다.

 

출력

각 줄에 하나씩, 거스름돈으로 줄 5만원권, 1만원권, 5천원권, 1천원권, 5백원, 100원, 50원, 10원 짜리의 개수를 공백으로 구분하여 출력한다.

 

---

2. 문제 설계

탐욕법(Greedy) 알고리즘을 사용하여 풀이한다.

1) 받은 돈에서 물건 값을 뺀다.

2) 거스름돈에서 가장 큰 단위부터 나누어 몫은 출력하고 나눈 나머지는 거스름돈이 된다.

3) 이 과정을 가장 작은 단위인 10으로 나눌 때까지 반복한다.

---

3. 구현

#include<iostream>
#include<vector>
#include<string>
using namespace std;

vector<int> solve(int value, int money) {
 vector<int> result(8, 0);
 vector<int> changes = { 50000,10000,5000,1000,500,100,50,10 };
 int i = 0, cnt = 0;
 money = money - value;
 while (money != 0) {
  result[i] = money / changes[i];
  money = money % changes[i];
  i++;
 }
 return result;
}

int main() {
 int testCase;
 string input;
 int value, money;
 getline(cin, input);
 testCase = atoi(input.c_str());
 vector<vector<int>> answer(testCase);
 for (int i = 0; i < testCase; i++) {
  cin >> value >> money;
  answer[i] = solve(value, money);
 }
 for (int i = 0; i < testCase; i++) {
  for (int j = 0; j < 8; j++) {
   cout << answer[i][j] << ' ';
  }
  cout << '\n';
 }
 return 0;
}

---

4. 테스트