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

문제 링크

---

1. 문제 풀이

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

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

---

2. 코드

1. Bottom-Up 토글링 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];  // 토글링 dp
            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 토글링 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));  // 토글링 dp
        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';
    }
}

---

3. 풀이 정보

1. Bottom-Up 토글링 dp [Java]

언어	시간	메모리	코드 길이
Java 11	2224 ms	22008 KB	1669 B

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

언어	시간	메모리	코드 길이
Java 11	1512 ms	18956 KB	1420 B

3. Bottom-Up 토글링 dp [C++]

언어	시간	메모리	코드 길이
C++ 17	472 ms	3292 KB	1138 B

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

언어	시간	메모리	코드 길이
C++ 17	440 ms	2528 KB	873 B

---