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

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

 

---

해설

그리디 문제인데 DP로도 풀 수 있다.

 

5원을 최대한 많이 거슬러 주어야한다.

어떻게 최대한 많이 거슬러 줄 수 있을까?

 

첫번째 방법은 2원씩 n에서 빼본다. 그러다가 5로 나누어 떨어지면 정답을 출력한다.

두번째 방법은 A(n / 5)개의 동전에서(5원의 개수) n - A가 홀수라면 --A 해주고 짝수라면 2로 나눈 몫을 출력한다.

5원을 최대한 많이 주어야 하기때문에 A의 개수를 줄여가보면서 개수를 세어보는 것이다.

세번째 방법은 DP이다. n원의 최소 값은 min(n - 2, n - 5) + 1이다.

만약 11원의 경우 9원에서 2원을 더한 것, 6원에서 5원을 더한 것 중 최소 값을 고르면 되는 것이다.

메모이제이션을 활용한 DP이고 Bottom-Up방식으로 풀 수 가 있다.

 

---

코드

 

2원씩 빼면서 5원으로 나누어 떨어진다면

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n = 0, cnt = 0;
    cin >> n;
    if (n % 5 == 0) cout << n / 5;
    else
    {
        while(n > 0)
        {
            n -= 2; ++cnt;
            if (n % 5 == 0)
            {
                cout << cnt + n / 5;
                break;
            }
        }
    }
    if (n < 0) cout << -1;
}

 

 

5원 최대 개수(A)를 n에서 뺏을 때 나머지가 1이라면 A를 하나 줄여보고 다시 계산해보고, 0이라면 A + (2원 최대 개수)로 정답을 출력한다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n; cin >> n;
    int f = n / 5;
    if (n % 5 == 0)
    {
        cout << f;
        return 0;
    }
    while (f >= 0)
    {
        int ret = (n - (f * 5)) % 2;
        int t = (n - (f * 5)) / 2;
        if (ret == 0)
        {
            cout << f + t;
            return 0;
        }
        f--;
    }
    cout << -1;
    return 0;
}

 

 

마지막 DP풀이이다. 각각의 최적해가 전체 문제의 최적해를 구하는데 사용. 메모이제이션.

코드는 크게 어렵지 않다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, i, j; cin >> n;
    vector<int> arr; arr.resize(n + 1);
    for (int i = 0; i <= n; ++i) arr[i] = -1;
    arr[2] = 1; arr[5] = 1;
    for (int i = 3; i <= n; ++i)
    {
        if (arr[i - 2] != -1) arr[i] = arr[i - 2] + 1;
        if (arr[i - 5] != -1 && i > 5) arr[i] = min(arr[i], arr[i - 5]+1);
    }
    cout << arr[n];
    return 0;
}