본문 바로가기

알고리즘 관련/BOJ

BOJ)10881 프로도의 선물 포장

문제: icpc.me/10881


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


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


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <algorithm>
using namespace std;
pair<intint> 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 % == j % || j % == k % || k % == i % 3)continue;
                    r = min(r, three(i, j, k));
                    r = min(r, twoonone(i, j, k));
                }
            }
        }
        printf("%d\n", r);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)5651 완전 중요한 간선  (0) 2017.06.12
BOJ)1626 두 번째로 작은 스패닝 트리  (5) 2017.06.12
BOJ)11689 GCD(n,k) = 1  (1) 2017.06.10
BOJ)2503 숫자 야구  (1) 2017.06.08
BOJ)1799 비숍  (0) 2017.06.08