[C++] 5585번. 거스름돈

그리디 알고리즘의 첫 문제를 풀어봤다. 

---

문제 분석

그리디 알고리즘의 문제이다.

타로가 지불한 돈을 입력받아 1000엔에서 뺀 값(change)을 잔돈으로 치환하는 문제이다.

문제를 보면 '언제나 거스름돈 개수가 가장 적게 잔돈을 준다'라는 구문이 있다. 보통 그리디 알고리즘은 '가장 적게'나 '가장 많게' 이런 식으로 많이 나온다고 하던데 문제를 잘 살펴보면 쉽게 찾을 수 있다. 

 

알고리즘 설계

잔돈(500, 100, 50, 10, 5, 1)들을 배열이나 벡터에 담아서 쭈루룩 훑는 방식이 편하다.

큰 순으로 담아야 잔돈 개수가 적어지므로, 500부터 벡터에 담았다.

 

change를 잔돈으로 나눈 몫-> 동전 개수

change를 잔돈으로 나눈 나머지-> 새로운 change

 

이 구문을 반복한다. 

 

아래는 예제를 풀어본 그림이다. 

 

코드

#include <iostream>
#include <vector>
using namespace std;
/*
1. 지불할 돈을 입력받음
2. 거스름돈이 가장 적게 잔돈을 만든다.

*/
int main() {
    //1
    int pay;
    cin >> pay;

    //2
    int change = 1000 - pay;
    vector <int> cointype = { 500, 100, 50, 10, 5, 1 };
    int coin = 0; //동전개수
    for(int i=0; i<6; i++) {
        if (change==0) break;
        coin+=change / cointype[i];
        change=change% cointype[i];
    }
    cout << coin << '\n';

    return 0;
}

 

느낀 점

그리디 알고리즘임을 인지하고 푼 문제는 이번이 처음이다.

보통 코딩테스트에서는 알고리즘(그리디, 탐색, 기초동적)만 잘 다져두면 기본적인 실력은 된다고 한다.

앞으로 각각 50문제씩 풀어보려고 한다.