[ 백준 14916 ] 거스름돈 (C++)

백준의 거스름돈(14916) 문제이다.

[ 문제 바로가기 ]

 

[ 문제풀이 ]

주어진 돈을 2원과 5원을 이용해서만 줄 때, 사용해야 되는 동전의 최소갯수를 구해야 하는 문제이다.

여러가지 케이스들을 통해서 문제에 접근해보자.

 

#Case1 : 5원만 이용해서 해결하기

우리는 2원과 5원만 이용해서 주어진 돈을 줘야한다. 그리고 이 때 동전의 갯수를 최소화 시켜야 한다.

그렇다면, 이는 5원짜리 동전을 최대한 많이 사용하는 것이 유리하다는 것을 직관적으로 알 수 있다.

예를 들어서 주어진 금액이 20원이라고 가정해보자. 이 경우에는 딱 봐도 5원짜리 4개를 이용해서 20원을 만드는 것이 사용한 동전의 갯수를 최소화 시키는 Case가 될 것이다. 아무리 2원짜리를 넣고 5원짜리를 어떻게 한다고 하더라도, 이것보다 동전을 덜 사용할 수는 없다.

즉 ! 주어진 돈이 5로 나누어 떨어지는 금액이라면, 지불해야 하는 동전의 최소 갯수는 "금액 / 5" 개가 될 것이다.

# 주어진 금액 N 이 5로 나누어 떨어지는 금액이라면, 지불해야 하는 동전의 최소갯수 = N / 5개.

 

#Case2 : 5원을 최대한으로 사용 후, 2원을 이용해서 해결하기

너무나도 당연하게도 5원 만으로 해결이 불가능한 금액도 있을 것이다.

하지만, 핵심은 "최대한 5원짜리 동전을 많이 사용하는 것" 이라는 것을 생각하면서 진행해보자.

14원을 한번 예로 들어보자.

14원 같은 경우에는 5원짜리 동전 2개와 2원짜리 동전 2개, 총 4개의 동전을 이용해서 만들 수 있다.

그럼 어떻게 이를 구할 수 있을지 이야기를 해보자.

먼저, 5원짜리 동전을 최대한 많이 사용하는 것이 유리하다는 것을 알고 있으니, 14원을 5원짜리 동전으로 먼저 채워보자.

그럼, 5원짜리 동전 2개를 이용해서 10원을 채울 수 있을 것이다. 3개를 사용하는 순간 15원이 되므로 주어진 14원보다 더 커지기 때문에 5원짜리 동전은 최대 2개만 사용이 가능할 것이다.

그렇게 되면 10원이 5원짜리 동전에 의해서 채워지고 4원이 남게 될 것이다.

이 남은 4원을 2원짜리 동전으로 채우게 되면 정답을 구할 수가 있다.

즉 ! 주어진 금액이 5원으로 나누어 떨어지지 않는다면, 가장 우선적으로 5원으로 모두 채운 후에 남은 금액을 2원짜리 동전으로 채워주면 된다. 하지만 이 경우가 항상 적용이 되는 것은 아니다.

이 Case2는 "주어진 금액을 5원으로 먼저 채운 후, 남은 금액을 2원으로 채울 수 있을 '때'만 가능한 계산이다./

# 주어진 금액 N이 5로 나누어 떨어지지 않는다면, 1차적으로 5원으로 N을 최대한 채워보자.
# 채우고 남은 금액을 2원으로 채울 수 있다면, 2차적으로 남은 금액을 2원으로 채우자.
# 최종적으로 지불해야 하는 동전의 최소갯수 = (N / 5) + (N % 5) / 2

 

#Case3 : Case1, 2에 의해서 해결이 안되는 경우

Case2에서는 해결이 안되는 경우이다.

Case2에서는 주어진 금액 N을 5원으로 먼저 채우고, 남은 금액을 2원으로 채울 수 있을 때의 이야기이다.

하지만 2원으로 채울 수 없는 경우가 존재한다.

13원을 예시로 한번 들어보자.

Case2의 말대로 먼저 13원을 5원으로 채우게 되면, 5원 2개를 사용해서 10원을 채우고, 남은 3원을 2원으로 채우면 될 것이다.

하지만 ? 3원은 2원짜리 동전만으로는 채울 수가 없다.

이 경우에는 어떻게 해야할까?? 5원짜리 동전을 저렇게 최대로 채우면 안되는 것이다.

이런 경우에는 채웠던 5원짜리 동전 중 하나를 뺀 금액을 만들어주자.

다시 이야기해보자. 13원을 5원짜리 2개를 사용해서 10원을 만든 후에, 나머지 3원을 계산하려고 봤더니, 3원이 계산이 안되었다. 이 상황에서 5원짜리 동전을 하나 빼버리면 5원짜리 동전은 1개만 사용한 격이 되고, 결국 8원이 남게 된다.

8원은 Case2와 같이 2원으로 해결이 가능한 경우이다.

그럼 이게 왜 가능한 것일까 ?? 왜 5원으로 채우고 남은 금액이 홀수인 경우에는 다시 5원만 플러스를 시켜준다면 반드시 2원으로 그 금액을 채울 수 있을까 ??

왜냐하면 홀수 + 홀수 = 짝수 이기 때문이다. 2원으로 만들 수 있는 금액은 반드시 짝수일 것이다. 홀수 중에 2원으로 만들 수 있는 금액은 존재하지 않는다.

또한, 홀수 + 홀수는 반드시 짝수가 나오게 된다. 즉 ! 5원을 채울만큼 최대한으로 채우고 남은 금액이 홀수라면, 2원으로 채울 수 없으니 5원짜리 동전을 하나 빼서 해당 금액에 + 5원을 한 효과를 줘버리게 되면 결과적으로 남은 금액이 홀수 + 홀수가 되어서 반드시 짝수가 나오게 될 것이고, 이는 무조건 2원으로 해결이 가능하다는 것이다.

# 주어진 금액 N이 5로 나누어 떨어지지 않는다면, 1차적으로 5원으로 N을 최대한 채워보자.
# 채우고 남은 금액을 2원으로 채울 수 없다면, 2차적으로 남은 금액에 5원을 더해주자.
# 5를 더해주는 이유는, 5원짜리 동전을 하나 뺀 것과 같은 효과이다.
# 최종적으로 지불해야 하는 동전의 최소갯수 = (N / 5) - 1 + (N % 5 + 5) / 2

 

#Case4 : 해결이 불가능한 경우

해결이 불가능한 금액은 딱 2가지가 있다.

첫번째로, "1원"이 주어졌을 때이다. 1원은 2원과 5원을 이용해서 만들 수 없는 금액이다. 따라서 해결이 불가능하다.

두번째로, "3원"이 주어졌을 때이다. 3원은 2원을 이용해서 만들수도 없고, 5원보다는 작은 금액이라서 5원을 이용해서도 만들 수 없는 금액이다. 따라서 1원과 3원이 주어졌을 때에는 -1을 return 해주자.

 

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N, Answer;
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    if (N == 1 || N == 3)
    {
        cout << -1 << endl;
        return;
    }
 
    if (N % 5 == 0)
    {
        cout << N / 5 << endl;
        return;
    }
 
    int Five_Coin = N / 5;     N %= 5;
    if (N % 2 == 0) Answer = Five_Coin + N / 2;
    else
    {
        Five_Coin--;
        N += 5;
        Answer = Five_Coin + N / 2;
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}