2839 설탕 배달

전에는 5로 나누고 3으로 나누는 식으로 푼 것 같은데 문득 dp를 써보고 싶었다. 

 

코드는 아래처럼 짰는데..

 

#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 dp[5005];

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

    for (int i = 3; i <= n; i++)
    {
        int check = dp[i - 3];

        if (i >= 5)
            check = min(check, dp[i - 5]);

        dp[i] = check + 1;
    }

    cout << dp[n] << endl;

    return 0;
}

 

음.. 잘 작동 안 하는 것 같다.

 

문제가 4처럼 안 나눠떨어지는 경우인데 어찌할지 모르겠음

 

---

이 문제를 처음부터 DP..! DP로 해결해야지...!!!! 마음먹어서 잘 못 풀었던 것 같음

 

DP는 왜 이름부터 다이나믹-프로그래밍인거냐고. 괜히 뭔가 있다고 기대하게 만들잖아. (메모이제이션 씁시다)

 

그래서 다시 재귀로 풀어보기로 마음먹었다. 

 

하지만 깨달았다.. 난 재귀도 잼병인거슬,,, 

 

int func(int x)
{
    if (x < 0)
        return 3000;

    if (x == 0)
        return 0;

    if (x == 1 || x == 2)
    {
        return 3000;
    }

    return min(func(x - 3), func(x - 5)) + 1;
}

 

결국에는 잘 짜긴 했지만 처음에는 따로 fail = false라는 변수를 두고 x == 1 || x == 2일 때 fail = true로 만들었다. 

 

항상 fail이 뜨길래 뭐지....? 싶었는데 그려보니깐 알겠다. 결과가 2가 되는 경우가 있어서 그렇구나.

 

 

 

이제 메모이제이숀- 을 써서 2^n번 확인하지 못하게 만들어봅시다. 

 

#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);
    v[0] = 0;
    v[1] = 3000;
    v[2] = 3000;

    for (int i = 3; i <= n; i++)
    {
        int tmp1, tmp2;

        tmp1 = v[i - 3];
        if (i < 5)
            tmp2 = 3000;
        else
            tmp2 = v[i - 5];

        v[i] = min(tmp1, tmp2) + 1;
    }

    if (v[n] > 3000)
        cout << -1 << endl;
    else
        cout << v[n] << endl;

    return 0;
}

 

DP로 바꾸는 건 쉬웠다

 

 

뿌듯해

 

 

---

DP는 바텀업이 아닙니다...!!!!!

 

메모이제이션 활용해서 재귀로도 짤 수 있다. 

 

ㅋㅋㅋㅋ 완전 간단해졌음 

 

#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>;

vector<int> v(5005, -1);

int func(int x)
{
    if (x < 0)
        return 3000;

    if (x == 0)
        return 0;

    if (x == 1 || x == 2)
        return 3000;

    if (v[x] != -1)
        return v[x];

    v[x] = min(func(x - 3), func(x - 5)) + 1;;

    return v[x];
}

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

    func(n);
    
    if (v[n] > 3000)
        cout << -1 << endl;
    else
        cout << v[n] << endl;

    return 0;
}