[백준] 1801번 - 직사각형 만들기 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 막대를 이어 붙이는 것이 가능할 때 만들 수 있는 가장 큰 직사각형의 넓이를 구하는 문제다. $N$ 이 꽤 작긴하지만 각 변에 어떤 막대를 배치할지 찾는 단순한 완전탐색으로는 $O(5^N)$ 이라서 어렵다.(네 변 + 안 고르기로 총 5가지 선택지)

해당 문제는 4차원 dp를 활용해서 직사각형의 왼쪽 변은 $a$, 오른쪽 변을 $b$, 윗쪽 변을 $c$, 아랫쪽 변을 $d$ 라고 했을 때, 각 변에 각 차원을 부여한 후 완전탐색 및 가지치기를 하는 방식으로 해결했다. 먼저 주어진 막대의 길이의 합 $sum$ 을 구한 후 절반인 $half$ 를 구했다. 그러면 직사각형의 각 변은 $half$ 미만이어야 하고, 가로 한변과 세로 한변의 합도 최대 $half$ 까지만 가능하다. 또한 항상 $b$ 가 $a$ 보다 크거나 같게, $d$ 가 $c$ 보다 크거나 같게 dp 갱신을 하여 4중 반복문 순회 최적화도 수행했다.

완전 탐색 과정은 각 막대기에 대해 현재 가능한 케이스면 각 변에 막대기를 붙여서 조건에 맞으면 후보로 추가해줬다. 이때 $a \le b$, $c \le d$ 가 되게끔 설정하는 것과 직사각형 후보 조건을 검증한 후 가능하면 리스트에 추가한 후 한번에 갱신해줬다.

4차원 dp 갱신이 끝나면 이제 직사각형이 가능한지 2중 반복문으로 탐색하여 가능한 경우마다 최댓값을 갱신해주면 된다.

---

2. 코드

1. Bottom-Up 4차원 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[] arr = new int[N];
        int sum = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            sum += arr[i] = Integer.parseInt(st.nextToken());
        }
        int half = sum / 2;  // 전체 막대 길이의 절반

        boolean[][][][] dp = new boolean[half][half][half][half];  // 각 변은 전체 막대 길이의 절반 미만이어야 함
        dp[0][0][0][0] = true;

        for (int n : arr) {
            List<int[]> list = new ArrayList<>();

            // b, d는 항상 a, c보다 길게 저장하여 탐색 범위 축소
            for (int a = 0; a < half; a++) {
                for (int b = a; b < half; b++) {
                    for (int c = 0; c < half; c++) {
                        for (int d = c; d < half; d++) {
                            if (!dp[a][b][c][d]) continue;  // 현재 불가능한 케이스면 넘김

                            // a에 막대를 붙이려고 할 경우 a + n이 b보다 작으면 붙이고 크면 붙이되 순서를 뒤바꿔서 항상 b가 더 크게 저장
                            if (Math.max(a + n, b) < half)
                                list.add(new int[]{Math.min(a + n, b), Math.max(a + n, b), c, d});

                            // b에 막대를 붙이려고 할 경우 half 보다 작으면서 인접한 변과의 합도 half 이하여야 함
                            if (b + n < half && b + n + d <= half) list.add(new int[]{a, b + n, c, d});

                            // c에 막대를 붙이려고 할 경우 c + n이 d보다 작으면 붙이고 크면 붙이되 순서를 뒤바꿔서 항상 d가 더 크게 저장
                            if (Math.max(c + n, d) < half)
                                list.add(new int[]{a, b, Math.min(c + n, d), Math.max(c + n, d)});

                            // d에 막대를 붙이려고 할 경우 half 보다 작으면서 인접한 변과의 합도 half 이하여야 함
                            if (d + n < half && d + n + b <= half) list.add(new int[]{a, b, c, d + n});
                        }
                    }
                }
            }

            // 가능한 후보들로 dp 갱신
            for (int[] pos : list) {
                dp[pos[0]][pos[1]][pos[2]][pos[3]] = true;
            }
        }

        int max = -1;
        for (int h = 1; h < half; h++) {
            for (int w = 1; w < half; w++) {
                if (dp[h][h][w][w]) {
                    max = Math.max(max, h * w);
                }
            }
        }

        System.out.println(max);
    }
}

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

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

bool dp[80][80][80][80];

struct Node {
    int a, b, c, d;
};

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

    int n;
    cin >> n;

    vector<int> v(n);
    for (int& x : v) cin >> x;

    int sum = 0;
    for (int x : v) sum += x;

    int half = sum / 2;  // 전체 막대 길이의 절반
    dp[0][0][0][0] = true;

    for (int x : v) {
        vector<Node> tmp;

        // b, d는 항상 a, c보다 길게 저장하여 탐색 범위 축소
        for (int a = 0; a < half; a++) {
            for (int b = a; b < half; b++) {
                for (int c = 0; c < half; c++) {
                    for (int d = c; d < half; d++) {
                        if (!dp[a][b][c][d]) continue;  // 현재 불가능한 케이스면 넘김

                        // a에 막대를 붙이려고 할 경우 a + n이 b보다 작으면 붙이고 크면 붙이되 순서를 뒤바꿔서 항상 b가 더 크게 저장
                        if (max(a + x, b) < half) tmp.push_back({min(a + x, b), max(a + x, b), c, d});

                        // b에 막대를 붙이려고 할 경우 half 보다 작으면서 인접한 변과의 합도 half 이하여야 함
                        if (b + x < half && b + x + d <= half) tmp.push_back({a, b + x, c, d});

                        // c에 막대를 붙이려고 할 경우 c + n이 d보다 작으면 붙이고 크면 붙이되 순서를 뒤바꿔서 항상 d가 더 크게 저장
                        if (max(c + x, d) < half) tmp.push_back({a, b, min(c + x, d), max(c + x, d)});

                        // d에 막대를 붙이려고 할 경우 half 보다 작으면서 인접한 변과의 합도 half 이하여야 함
                        if (d + x < half && d + x + b <= half) tmp.push_back({a, b, c, d + x});
                    }
                }
            }
        }

        // 가능한 후보들로 dp 갱신
        for (auto& s : tmp) {
            dp[s.a][s.b][s.c][s.d] = true;
        }
    }

    int mx = -1;
    for (int h = 1; h < half; h++) {
        for (int w = 1; w < half; w++) {
            if (dp[h][h][w][w]) {
                mx = max(mx, h * w);
            }
        }
    }

    cout << mx;
}

---

3. 풀이 정보

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

언어	시간	메모리	코드 길이
Java 11	836 ms	359376 KB	2890 B

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

언어	시간	메모리	코드 길이
C++ 17	240 ms	107680 KB	2251 B

---