[BOJ 1801] 직사각형 만들기

https://www.acmicpc.net/problem/1801

1801번: 직사각형 만들기

Tag : knapsack, optimization

 

문제요약

주어진 막대를 조합해 만들 수 있는 가장 큰 직사각형의 넓이를 구하라. \((N \leq 16)\)

 

풀이

직관적으로 떠올릴 수 있는 풀이는 다음과 같다. 

D[a][b][c][d] = 막대를 중복되지 않게 합쳐 a, b, c, d를 만들 수 있는가

이때 시간복잡도는 \(O(N \times 80^4) = 655360000 \)이 될 것이다. 

 

두가지 최적화를 한다면 위의 풀이에서 30배정도 빠른 코드를 만들 수 있다.

1. \((a, b), (c, d)\)는 각각 단조성 유지

2. \(a + b \leq sum, b + d \leq \frac{N}{2} \)조건을 통해 가지치기

[1], [2]를 모두 만족하는 (a, b, c, d) 순서쌍의 개수 c는 아래와 같이 구할 수 있다.

 

\(c = \sum_{b=0}^{80}{ \sum_{d=0}^{80-b}{ \{\sum_{a=0}^{80}{ [a \leq b] } \times \sum_{c=0}^{80}{ [c \leq d] } \} } } \)

 

\(= \sum_{b=0}^{80}{ \sum_{d=0}^{80-b}{ \{min(\sum{v[i]} - b, b) \times min(\sum{v[i]} - d, d) \} }} \)

 

\(= 20821440 \)

 

때문에 아래 코드가 \(O(2e7)\)정도에 돌아간다는 것을 알 수 있다. 

+ 벡터 + 분기마다 처리를 네다섯번씩 해서 상수가 좀 붙는 듯하다.

 

전체코드

#include "bits/stdc++.h"

using namespace std;
using ll = long long;

int sum = 0;
int v[22];
int D[81][81][81][81];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);
    
    int n; cin >> n;
    for(int i=1; i<=n; sum += v[i++]) cin >> v[i];
    D[0][0][0][0] = 1;
    for(int t=1; t<=n; t++) {
        int x = v[t];
        vector<tuple<int, int, int, int>> v;
        for(int i=0; i<=sum; i++) for(int j=i; i+j<=sum; j++) {
            for(int k=0; k<=sum; k++) for(int p=k; k+p<=sum; p++) {
                if(2 * (j + p) > sum) continue;
                if(D[i][j][k][p]) continue;
                if(i >= x and D[i - x][j][k][p]) v.emplace_back(i, j, k, p);
                else if(j >= x and D[min(i, j - x)][max(i, j - x)][k][p]) v.emplace_back(i, j, k, p);
                else if(k >= x and D[i][j][k - x][p]) v.emplace_back(i, j, k, p);
                else if(p >= x and D[i][j][min(k, p - x)][max(k, p - x)]) v.emplace_back(i, j, k, p);
            }
        }
        for(auto &[a, b, c, d] : v) D[a][b][c][d] = 1;
    }
    int ans = 0;
    for(int i=1; i<=80; i++) for(int j=1; j<=80; j++) {
        if(D[i][i][j][j]) ans = max(ans, i * j);
    }
    cout << (ans ? ans : -1) << endl;
}