백준 13910, 개업

개요

문제 링크
골드 5, DP
최대 2개의 바구니를 사용해 물건을 옮기는 최소 횟수

---

접근

1. 최대 2개까지만 사용가능하다. 문제 잘못읽었다가 메모이제이션 + 재귀로 꽤나 고생했다.

2. dp에 들어갈 값은 n개 작업을 완료하는데에 필요한 최소 세트 수, 세트란? 1개 또는 2개를 사용하는 횟수를 말한다. 예를 들어,

   // n = 5, m = {1,3}
   5 = {1,3}+{1}

   2개의 세트를 사용하였다. 웍은 두개까지 사용가능하므로 n개 작업을 완료하려면 n-w[i] 혹은 n-w[i]-w[j]에서 +1을 한 값의 최솟값만큼의 세트가 필요할 것이다.

3. 따라서 업데이트는 dp[n-w[i]]+1, dp[n-w[i]-w[j]]+1과 비교해 해주면 된다.

---

Pseudo code

dp[n] = minimum_set

for (i = 0~m)
    if (n - w[i] >= 0)
        dp[n] = min(dp[n], dp[n-w[i]]+1)
    for (j = 0~i)
        if (n - w[i] - w[j] >= 0)
            dp[n] = min(dp[n], dp[n-w[i]-w[j]]+1)

---

Source code

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int a[m], dp[n+1];
    for (int i=0; i<m; i++)
        cin >> a[i];
    for (int i=1; i<=n; i++)
        dp[i] = 2e9;
    dp[0] = 0;
    for (int i=1; i<=n; i++)
        for (int j=0; j<m; j++) {
            if (i-a[j]>=0)
                dp[i] = min(dp[i],dp[i-a[j]]+1);
            for (int k=0; k<j; k++)
                if (i-a[j]-a[k]>=0)
                    dp[i] = min(dp[i],dp[i-a[j]-a[k]]+1);
        }
    cout << (dp[n]==2e9?-1:dp[n]);
}