BOJ)10881 프로도의 선물 포장

문제: icpc.me/10881

세개의 상자를 하나의 큰 포장상자안에 넣어야 할 때 준비해야하는 포장상자의 최소 넓이를 구하는 문제이다.

우선 상자가 세개밖에 주어지지 않기 때문에 완전탐색을 생각해볼 수 있다.

세개의 상자를 배치하는 모양은 회전에 따라서 달라지지 않는 경우는 1열로 3상자를 배치하는 케이스와 2상자 위에 1 상자를 쌓아놓는 모양 두가지 밖에 없다.

때문에 주어진 조건으로 위의 경우에 해당 하는 모든 경우를 탐색하면 하나의 쿼리를 2*6^3의 시간만에 처리할 수 있다.

#include <cstdio>
#include <algorithm>
using namespace std;
pair<int, int> a[6];
int three(int i,int j,int k) {
    int l = a[i].first + a[j].first + a[k].first;
    int r = max(a[i].second, max(a[j].second, a[k].second));
    return l*r;
}
int twoonone(int i, int j, int k) {
    int l = max(a[i].first, a[j].first) + a[k].first;
    int r = max(a[i].second + a[j].second, a[k].second);
    return l*r;
}
int t;
int main() {
    scanf("%d", &t);
    while (t--) {
        for (int i = 0; i < 3; i++) {
            scanf("%d%d", &a[i].first, &a[i].second);
            a[i + 3].first = a[i].second;
            a[i + 3].second = a[i].first;
        }
        int r = 1e9;
        for (int i = 0; i < 6; i++) {
            for (int j = 0; j < 6; j++) {
                for (int k = 0; k < 6; k++) {
                    if (i % 3 == j % 3 || j % 3 == k % 3 || k % 3 == i % 3)continue;
                    r = min(r, three(i, j, k));
                    r = min(r, twoonone(i, j, k));
                }
            }
        }
        printf("%d\n", r);
    }
    return 0;
}