13902 개업 2

BOJ::13902 개업 2

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

1. a벡터에 m개의 웍에 대한 정보 입력

2. m개의 웍들 중 2개의 조합으로 만들 수 있는 경우에 대해 a에 추가로 푸쉬

3. 만들어진 a벡터를 가지고 dp를 활용하여 d[n] 에 대한 최소값 찾아 출력 

ex) v = {1,3,5} : d[10] = min(d[10-1],d[10-3],d[10-5]) +1

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> a(m);
    vector<bool> check(n + 1, false);
 
    // a벡터에 m개 입력 받는다
    while (m--) {
        scanf("%d", &a[m]);
        check[a[m]] = true;
    }
 
    // 조건에 벗어나지 않으면서, 
    // 두 웍의 합으로 만들 수 있는 모든 경우에 대해 저장
    int sz = a.size();
    for (int i = 0; i < sz - 1; i++) {
        for (int j = i + 1; j < sz; j++) {
            int v = a[i] + a[j];
            if (v > n || check[v]) continue;
            check[v] = true;
            a.push_back(v);
        }
    }
     
    // 짜장면 N그릇을 만드는 최소비용을
    // 다이나믹으로 찾는다.
    vector<int> d(n + 1, 0);
    for (int i = 0; i < a.size(); i++) {
        d[a[i]] = 1;
        for (int j = a[i] + 1; j <= n; j++) {
            if (d[j - a[i]] == 0) continue;
            if (d[j] == 0 || d[j] > d[j - a[i]] + 1) 
                d[j] = d[j - a[i]] + 1;
        }
    }
 
    if (d[n] == 0) printf("-1\n");
    else printf("%d\n", d[n]);
}