Brute Force -10881 C++

문제

---

프로도는 네오에게 줄 생일 선물을 세 개 샀다. 이 세 개의 선물은 직사각형 모양의 선물 상자에 각각 하나씩 담겨 있다.
프로도는 이 선물들을 적당한 크기의 직사각형 포장 상자에 넣어 포장하려 한다.
큰 포장 상자를 주문할수록 돈을 더 많이 써야 하기 때문에, 프로도는 최대한 작은 상자에 세 개의 선물을 모두 담으려고 한다.
(중략)
구매한 선물 상자들의 크기가 주어졌을 때, 선물들을 안전하게 포장하는 데 필요한 포장 상자의 최소 크기 (즉, 포장 상자의 넓이가 최소가 되는 경우)를 구하시오
https://www.acmicpc.net/problem/10881

10881번: 프로도의 선물 포장

 

과정

---

이전 문제에서도 풀어본 완전탐색 문제이다.
풀면서 느끼는 건데 확실히 완전탐색 문제는 생각하는 일련의 과정이 난해한 문제들이 많은 것 같다. 
(대부분 최대한 무식하게 생각해서 풀면 되긴 하는듯..)
 
선물상자가 배치될 수 있는 경우의 수는 하나 당 세운 것과 눕힌 것 '두 개' 의 경우가 될 것이다.

선물 상자의 개수는 다행히도 세개로 고정되어 있으므로 선택할 수 있는 경우의 수는 6³

연산의 최대치가 높지 않으므로 3중 반복문을 사용할 것이다.
 
상자 세개를 배치하는 방법은,, 잘 생각해보면
1. 세 상자를 모두 나란히 배치
2. 두 개의 상자 위에 하나의 상자를 배치
두 가지만 생각해줘도 모든 경우의 수를 생각 할 수 있다.
 
3중 반복문 안에서 서로 같은 상자를 배치하는 경우를 제외시키고, 서로 다른 상자일 경우
위의 두가지 경우를 계산해서 최솟값을 출력하면 문제가 해결된다.
 
자센한 사항은 주석을 달아놓았으니 참고하면 좋을 것 같다.
 
 

코드

---

#include <iostream>
using namespace std;

int height[7];
int width[7];

int calcu(){
    int answer=0;
    int ansheight;
    int answidth;
    for(int i = 1; i<=6; i++){
        for(int j = 1; j <=6; j++){
            for(int k = 1; k<=6; k++){
                //같은 상자가 들어가는 상황 제외..
                if(i%3 == j%3 || j%3 == k%3 || k%3 == i%3|| i==j || i==k || j==k){
                    continue;
                }
                //세개가 나란한 상황,, * i j k가 3이상 넘어가면 height와 width 반전되므로 상관x
                ansheight = height[i] + height[j] + height[k];
                answidth = max(max(width[i], width[j]), width[k]);

                if(answer == 0)
                    answer = ansheight*answidth;
                else{
                    answer = min(answer, ansheight*answidth);
                }

                //두 상자 위에 한개가 있는 경우
                //높이 = 위에 있는 상자 두 개 중에 높이 높은 상자 + 아래 있는 상자
                //가로 = 위에 있는 상자 두 개 더한 가로와 아래 있는 상자 중 더 긴 상자
                
                ansheight = height[i]+ max(height[j], height[k]);
                answidth = max(width[i],width[j]+ width[k]);
                answer = min(answer, ansheight*answidth);
            }
        }
    }
    return answer;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        for(int i = 1; i<=3; i++){
            cin >> width[i] >> height[i];
            width[i+3] = height[i];
            height[i+3] = width[i];
        }
        
        cout << calcu()<<'\n';
    }
}