[20/07/05] G. 개업 2 (13902)

 

디피~~~ 너무너무ㅠㅠㅠㅠㅠ 어렵다ㅠㅠㅠㅠ

 

이틀 걸려서 겨우겨우 풀었음

 

개념 잘 몰라서 ppt로 개념 서너번 읽고 블로그 글 읽고 거기 있는 백준 예제 풀어보고 그랬음ㅠ

 

물론 처음 접했을 때 어려운 건 알지만 그래도 ㅠ.ㅠ.ㅠ.ㅠ

 

 

 

이거 bottom up으로 하고 싶은데 어떻게 할지 몰라서 작년에 알고리즘 수업시간에 배운 거 사용해서 풀었다.

 

 

그리디 챕터 때 배운 건데 이 문제랑 비슷한 것 같음. 

 

코드는 되는대로 짰는데 잘 짰는지는 모르겠다. 디피 이렇게 하는 게 맞나? (memoization 쓰면 그게 다 디피겠지만)

 

엉엉헝헝 디피랑은 좀 더 친해져야겠다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

bool desc(int a, int b){ return a > b; };

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    vector<int> v(m);
    for (int i = 0; i < m; i++)
        scanf("%d", &v[i]);
    
    for (int i = 0; i < m-1; i++)
    {
        for (int j = i+1; j < m; j++)
        {
            if (v[i]+v[j] <= n)
                v.push_back(v[i]+v[j]);
        }
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    
    vector<int> d(n+1, 10005);
    d[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        set<int> s;
        for (int j = 0; j < v.size(); j++)
        {
            if (i - v[j] >= 0)
                s.insert(d[i - v[j]] + 1);
            else
                s.insert(10005);
        }
        d[i] = *s.begin();
    }

    if (d[n] >= 10005)
    {
        printf("-1");
        return 0;
    }
    printf("%d", d[n]);
    return 0;
}