[백준] 17528번 - Two Machines [Java][C++]

문제 링크

---

1. 문제 풀이

각각의 작업들에 대해 머신 $A$ 에서 작업하는 경우랑 머신 $B$ 에서 작업하는 경우랑 완료 시간이 다른데 전체 작업의 완료에 걸리는 최소 시간을 구해야 하는 문제다. 배낭 문제를 활용하면 이 문제를 해결할 수 있는데 배낭의 용량을 머신 $A$ 가 작업을 수행하는데 쓸 수 있는 최대 시간으로 했을 때, 배낭의 가치를 머신 $B$ 가 작업하는데 걸리는 최소 시간으로 설정하면 된다. 이러면 $\max(배낭의 용량, 배낭의 가치)$ 가 최소가 되는 경우를 찾는 문제로 생각해 볼 수 있다.

2차원 배열을 활용한 배낭 문제로 접근할 경우 예제 입력 1은 아래와 같이 구성할 수 있다.

1번 작업은 머신 $A$ 에서는 $2$, 머신 $B$ 에서는 $3$ 이 걸린다. 머신 $A$ 에 부여한 시간이 $2$ 보다 작으면 머신 $B$ 에서만 수행할 수 있으며, 머신 $A$ 에 부여한 시간이 $2$ 이상이면 머신 $A$ 에서 작업한다. 열 번호와 값 중 최댓값이 최대한 작아야하므로 머신 $A$ 에 여유 시간이 있으면 최대한 $A$ 에서 작업을 해 값인 머신 $B$ 의 작업 시간이 최소가 되게 해야 한다.

2번 작업은 머신 $A$ 에서는 $5$, 머신 $B$ 에서는 $3$ 이 걸린다. 머신 $A$ 에 부여한 시간이 $5$ 보다 작으면 2번 작업은 머신 $B$ 에서만 수행할 수 있으므로 머신 $B$ 에서 수행하고, 머신 $A$ 에 부여한 시간이 $5$ 이상이면 머신 $A$ 에서 하는 것과 머신 $B$ 에서 하는 것 중 어떤게 나은지 비교해봐야 한다.

이때 2번 작업의 소요 시간을 $t_A$, $t_B$ 라고 하고 현재 머신 $A$ 에 부여된 시간이 $T_A$ 라고 가정하자.

머신 $A$ 에서 작업하려면 이전 작업에서 머신 $A$ 에 부여된 시간이 $(T_A - t_A)$ 인 상황에서 머신 $A$ 에 작업을 맡기면 된다. 머신 $A$ 에 작업을 맡겼으므로 이전 작업에서 머신 $A$ 에 부여된 시간이 $(T_A - t_A)$ 인 상황에서 머신 $B$ 의 작업 시간을 그대로 가져오면 된다.

머신 $B$ 에서 작업하려면 이전 작업에서 머신 $A$ 에 부여된 시간이 $T_A$ 인 상황에서 머신 $B$ 에 작업을 맡기면 된다. 이전 작업에서 머신 $A$ 에 부여된 시간이 $T_A$ 인 상황이 머신 $B$ 의 작업 시간이 가장 짧으므로 여기서 머신 $B$ 에 작업을 맡기면 된다.

이를 점화식으로 나타내면 아래와 같이 된다.

\[dp[i][j] = \begin{cases} dp[i-1][j] + t_B, & j < t_A \\\\ \min \big(dp[i-1][j - t_A],\ dp[i-1][j] + t_B \big), & j \ge t_A \end{cases}\]

이런 과정을 쭉 반복하면 위와 같이 완성할 수 있으며 $\max(배낭의 용량, 배낭의 가치)$ 가 최소인 $4$ 만큼의 전체 시간으로 모든 작업을 완료할 수 있다.

---

2. 코드

1. Bottom-Up 2차원 dp [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[] A = new int[1 + N];
        int[] B = new int[1 + N];
        int sumA = 0;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            sumA += A[i] = Integer.parseInt(st.nextToken());
            B[i] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[1 + N][1 + sumA];
        for (int i = 1; i <= N; i++) {
            int a = A[i];
            int b = B[i];

            for (int j = 0; j <= sumA; j++) {
                if (j < a) {
                    dp[i][j] = dp[i - 1][j] + b;
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - a], dp[i - 1][j] + b);
                }
            }
        }

        int min = Integer.MAX_VALUE;
        for (int j = 0; j <= sumA; j++) {
            min = Math.min(min, Math.max(j, dp[N][j]));
        }

        System.out.println(min);
    }
}

2. Bottom-Up 1차원 dp [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[] A = new int[N];
        int[] B = new int[N];
        int sumA = 0;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            sumA += A[i] = Integer.parseInt(st.nextToken());
            B[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[1 + sumA];
        for (int i = 0; i < N; i++) {
            int a = A[i];
            int b = B[i];

            for (int j = sumA; j >= 0; j--) {
                if (j < a) {
                    dp[j] += b;
                } else {
                    dp[j] = Math.min(dp[j - a], dp[j] + b);
                }
            }
        }

        int min = Integer.MAX_VALUE;
        for (int j = 0; j <= sumA; j++) {
            min = Math.min(min, Math.max(j, dp[j]));
        }

        System.out.println(min);
    }
}

3. Bottom-Up 2차원 dp [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<pair<int, int>> v(n);
    for (auto& p : v) cin >> p.first >> p.second;

    int sum = 0;
    for (auto p : v) sum += p.first;

    vector<vector<int>> dp(1 + n, vector<int>(1 + sum));
    for (int i = 1; i <= n; i++) {
        int a = v[i - 1].first;
        int b = v[i - 1].second;

        for (int j = 0; j <= sum; j++) {
            if (j < a) {
                dp[i][j] = dp[i - 1][j] + b;
            } else {
                dp[i][j] = min(dp[i - 1][j - a], dp[i - 1][j] + b);
            }
        }
    }

    int mn = INT_MAX;
    for (int j = 0; j <= sum; j++) {
        mn = min(mn, max(j, dp[n][j]));
    }

    cout << mn;
}

4. Bottom-Up 1차원 dp [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<pair<int, int>> v(n);
    for (auto& p : v) cin >> p.first >> p.second;

    int sum = 0;
    for (auto p : v) sum += p.first;

    vector<int> dp(1 + sum);
    for (auto p : v) {
        int a = p.first;
        int b = p.second;

        for (int j = sum; j >= 0; j--) {
            if (j < a) {
                dp[j] += b;
            } else {
                dp[j] = min(dp[j - a], dp[j] + b);
            }
        }
    }

    int mn = INT_MAX;
    for (int j = 0; j <= sum; j++) {
        mn = min(mn, max(j, dp[j]));
    }

    cout << mn;
}

---

3. 풀이 정보

1. Bottom-Up 2차원 dp [Java]

언어	시간	메모리	코드 길이
Java 11	228 ms	76032 KB	1186 B

2. Bottom-Up 1차원 dp [Java]

언어	시간	메모리	코드 길이
Java 11	152 ms	14776 KB	1130 B

3. Bottom-Up 2차원 dp [C++]

언어	시간	메모리	코드 길이
C++ 17	68 ms	64516 KB	794 B

4. Bottom-Up 1차원 dp [C++]

언어	시간	메모리	코드 길이
C++ 17	20 ms	2268 KB	703 B

---