[백준(BOJ)] 5585번: 거스름돈 (그리디(Greedy) 알고리즘, C++)

✔ 거스름돈 개수가 가장 적게

---

• 그리디 알고리즘(Greedy Algorithm): 하나를 결정하는 그 순간에 최적이라고 생각하는 것을 선택해서, 최적해를 구하는 알고리즘이다.

• 500, 100, 50, 10, 5, 1에서 하나씩 결정할 때, 그 순간에 가장 많은 개수를 가질 수 있는 것을 택해서 카운팅에 더한다.

 

✔ 입출력

---

• 입력: 물건의 가격

• 출력: 잔돈에 포함된 매수 (총 몇 개의 지폐 또는 동전이 있는지)

 

✔ C++ 풀이

---

#include <iostream>

using namespace std;

int main()
{
    int price,i=0, count=0;
    int small_change[] = {500, 100, 50, 10, 5, 1};
    
    cin >> price;
    
    int change = 1000 - price;
    
    while(i<6){
        if(change >= small_change[i]){
            count += change / small_change[i];
        }
        change %= small_change[i++];
    }
    cout << count << endl;
}

• 배열에 500, 100, 50, 10, 5, 1 값의 잔돈을 넣어놓는다.

• change는 거스름돈에 해당한다. change가 잔돈 이상이어야 하므로  count에 추가하는 조건을 준다.

 

✔ 결과

---