[BaekJoon] 10982번 - 행운쿠키 제작소 [Java][C++]

문제 링크

---

1. 문제 풀이

BaekJoon 17528번 - Two Machines 문제와 거의 동일한 문제로 각각의 반죽들에 대해 오븐 1에서 굽는 경우랑 오븐 2에서 굽는 경우랑 걸리는 시간이 다른데 전체 반죽을 굽는데 걸리는 최소 시간을 구해야 하는 문제다. 배낭 문제를 활용하면 이 문제를 해결할 수 있는데 배낭의 용량을 오븐 1에서 굽는 데 쓸 수 있는 최대 시간으로 했을 때, 배낭의 가치를 오븐 2에서 굽는 데 걸리는 최소 시간으로 설정하면 된다. 이러면 $\max(배낭의\ 용량, 배낭의\ 가치)$ 가 최소가 되는 경우를 찾는 문제로 생각해 볼 수 있다.

반죽의 개수 $N$ 이 최대 $1,000$ 이고 반죽 당 굽는 데 걸리는 시간이 최대 $100$ 이어서 2차원 배열을 활용할 경우 메모리 초과가 발생하게 된다. 일종의 0/1 배낭 문제이므로 1차원 배열을 활용한 해법을 적용해도 되고, 롤링 배열 기법을 적용해도 메모리 문제를 해결할 수 있다.

---

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            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[2][1 + sumA];  // 롤링 배열
            int prev = 0;
            int cur = 1;
            for (int i = 0; i < N; i++) {
                int a = A[i];
                int b = B[i];

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

                // 롤링
                prev ^= 1;
                cur ^= 1;
            }

            int min = Integer.MAX_VALUE;
            for (int j = 0; j <= sumA; j++) {
                min = Math.min(min, Math.max(j, dp[prev][j]));  // 롤링 때문에 최신값이 prev에 있음
            }

            sb.append(min).append("\n");
        }

        System.out.println(sb);
    }
}

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            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]));
            }

            sb.append(min).append("\n");
        }

        System.out.println(sb);
    }
}

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

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

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

    int t;
    cin >> t;

    for (int tc = 1; tc <= t; tc++) {
        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(2, vector<int>(1 + sum));  // 롤링 배열
        int prev = 0;
        int cur = 1;
        for (int i = 0; i < n; i++) {
            int a = v[i].first;
            int b = v[i].second;

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

            // 롤링
            prev ^= 1;
            cur ^= 1;
        }

        int mn = INT_MAX;
        for (int j = 0; j <= sum; j++) {
            mn = min(mn, max(j, dp[prev][j]));  // 롤링 때문에 최신값이 prev에 있음
        }

        cout << mn << '\n';
    }
}

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

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

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

    int t;
    cin >> t;

    for (int tc = 1; tc <= t; tc++) {
        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 << '\n';
    }
}

---