[백준 17528] Two Machines

냅색 문제으로 풀 수 있는 문제인지 구별하는 게 어려웠다.

1. 풀이

문제에 주어진 두개의 값을 냅색문제 처럼 무게와 값어치로 하고 문제를 생각해보자. 여기서 무게를 \(A\)에게 일을 맡기는 대신 \(B\)에게 맡기는 것으로 해석이 가능하다.

그러면 dp값에 무엇이 저장되냐면

$$dp[t]=b\; \;A는\;t시간만큼을\;일하지\;않았을\;때,\;B가\;일한\;시간b$$

이렇게 정의할 수 있고, 그렇다면 \(A\)가 일을한 시간은 \((Sum_A−t)\)가 되므로, \(max(Sum_A−t,\;dp[t])\) 중 가장 작은 값이 답이 된다.

이 문제를 냅색문제로 생각할 수 있다는 것이 참신했다.

2.소스 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;


int n;
int arr[251][2];
int dp[251 * 251];


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


    memset(dp, 0x3f3f3f3f, sizeof(dp));
    dp[0] = 0;


    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int a, b; cin >> a >> b;
        sum += a;
        for (int i = 250 * 250; i >= a; i--)
            dp[i] = min(dp[i], dp[i-a] + b);
    }


    int ans = 0x3f3f3f3f;
    for (int i = 0; i <= sum; i++)
        ans = min(ans, max(sum-i, dp[i]));


    cout << ans;


    return 0;
}