BOJ 13910 : 개업

• 문제 링크 : boj.kr/13910
• 난이도 : G5
• 태그 : DP

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 987654321
#define int long long

using namespace std;

using ld = long double;
using pii = pair<int,int>;

template <typename T1, typename T2>
istream& operator>>(istream & ist, pair<T1,T2> &p) {
    ist >> p.first >> p.second;
    return ist;
}
template <typename T>
istream& operator>>(istream & ist, vector<T> &arr) {
    for(auto &u : arr) ist >> u;
    return ist;
}

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

    int n, m;
    cin >> n >> m;
    vector<int> arr(m);
    cin >> arr;

    set<int> _s;
    for(int i = 0; i < m; i++) {
        _s.insert(arr[i]);
        for(int j = i+1; j < m; j++) {
            _s.insert(arr[i]+arr[j]);
        }
    }

    vector<int> dp(n+1, INF);
    dp[0] = 0;
    for(int i = 0; i < n; i++) {
        for(auto u : _s) {
            int next = i+u;
            if(next <= n) dp[next] = min(dp[next], dp[i] + 1);
        }
    }
    cout << (dp[n] == INF ? -1 : dp[n]); 
    return 0;
}

---

풀이

동시에 두 개의 웍까지 사용할 수 있다.

두 가지의 웍을 동시에 사용하는 경우를 두 웍의 용량을 합한 하나의 웍을 사용하는 것으로 볼 수 있다.

이 경우 웍의 수는 M(M-1)/2이다.

여기까지 구하면 남은 건 전형적인 DP일 뿐이다.