17212 달나라 토끼를 위한 구매대금 지불 도우미

 

별 생각없이 큰 수 부터 빼다가 17원에서 불법지불 해버렸다..

 

3이 나와야 하는데 7, 7, 2, 1로 4를 지불해버린듯

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int     main()
{
    int n;
    scanf("%d", &n);

    int ans = 0;
    vector<int> coin = { 7, 5, 2, 1 };

    for (int i = 0; i < coin.size(); i++)
    {
        if (n / coin[i] > 0)
        {
            ans += n / coin[i];
            n %= coin[i];
        }
    }

    cout << ans << endl;

    return 0;
}

 

그래서 다시 그리디로 구현했다. 

 

으음 처음 동전문제 배울 때 그리디라 배웠는데 푸는 방법은 디피 아닌가?? 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int     main()
{
    int n;
    scanf("%d", &n);

    vector<int> v(n + 5);

    for (int i = 1; i <= n; i++)
    {
        if (i < 2)
            v[i] = v[i - 1] + 1;
        else if (i < 5)
            v[i] = min(v[i - 1], v[i - 2]) + 1;
        else if (i < 7)
            v[i] = min({v[i - 1], v[i - 2], v[i - 5]}) + 1;
        else
            v[i] = min({ v[i - 1], v[i - 2], v[i - 5], v[i - 7]}) + 1;
    }

    printf("%d\n", v[n]);

    return 0;
}