백준 14916번 거스름돈 - C++

문제

---

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

 

입력

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

 

출력

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

 

문제 링크

https://www.acmicpc.net/problem/14916

 

 

풀이

---

매우 간단한 문제다.

일단 최대한 5원짜리 동전을 많이 줘야 최소 개수로 동전을 줄 수 있으니 5원짜리 동전을 최대한 많이 준다. ▼

 

21원이 들어왔다고 했을 때, 5원짜리 4개를 주고 나면 애매하게 1원이 남는다.

2원짜리 동전으로 해결할 수 없는 상황이 온다. ▼

 

그러면 아까 배분했던 5원짜리에서 하나를 빼고 남아있던 1원에 더해줘서 6원을 만들어준다.

이렇게 되면 2원짜리 3개로 배분할 수 있게 된다. ▼

 

"그런데 5원짜리 하나 빼서 줬는데도 2원짜리로 안나눠지면 어떻게 해?"

 

 

결론만 말하자면 그런 일은 없다.

 

2로 나누어 떨어지지 않는 수는 무조건 홀수이다.

그리고 그 나누어 떨어지지 않는 수에 주는 수인 5도 홀수이다.

 

홀수에 홀수를 더하면 짝수가 나오기에, 5를 한번만 빼서 더해줘도 2로 나누어 떨어지게 된다. ▼

 

 

C++ 코드

---

#include <iostream>

using namespace std;

int N, answer, change;

void input() {
    cin >> N;
}

void solve() {
    answer = N / 5;
    change = N % 5;

    if (N < 5) {
        if (N % 2 == 0) {
            cout << N / 2;
        } else {
            cout << -1;
        }
    } else if (change % 2 != 0) {
        change += 5;
        answer--;
        answer += change / 2;
        cout << answer;
    } else {
        answer += change / 2;
        cout << answer;
    }
}

int main() {
    input();
    solve();
}