[C++] 백준 온라인 저지 5585번 거스름돈 풀이

거스름돈에 포함되는 잔돈의 갯수가 몇 개인지 구하는 문제 

 

---

문제의 조건

 

1. 1원 이상 1000원 미만의 지불해야 하는 금액이 주어진다. 

 

2. 잔돈의 종류는 500, 100, 50, 10, 5, 1원이 있다. 

 

2. 1000원 짜리를 냈을 때 받을 거스름돈에서 각 잔돈을 몇 개를 써서 받으면 최소로 받는지 구해서 출력 

 

---

풀이 과정

 

앞서 풀었던 몇 문제와 비슷하게 남은 돈에서 가능한 가장 큰 액수의 잔돈을 먼저 뺀 다음에 

그 다음 작은 액수의 잔돈과 비교해서 또 빼고 하는 방식으로 잔돈의 갯수를 구했습니다. 

 

 

---

 

 

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    
    vector<int> changes{500, 100, 50, 10, 5, 1};
    
    int change = 1000 - N;
    int answer = 0;
    int i = 0;
    while (0 < change)
    {
        if (changes[i] <= change)
        {
            //현재 인덱스의 잔돈을 최대 몇 개까지 포함할 수 있는지 구한다. 
            int count = change / changes[i];
            answer += count;
            //구하고 나면 그만큼 남은 돈에서 빼기 
            change -= count * changes[i];
        }
        else
        {
            i++; //현재 인덱스가 남은 돈보다 크면 다음 인덱스(더 작은 값) 탐색
            if (changes.size() <= i)
                i = changes.size() - 1;
        }
    }
    
    cout << answer;
    
    return 0;
}