백준 10881번 프로도의 선물 포장

문제 링크입니다: https://www.acmicpc.net/problem/10881

박스의 회전까지 고려해야했기 때문에 접근하기 까다로웠던 문제였습니다.

다행히 박스가 3개로 고정이였기 때문에 구현 자체는 크게 어렵지 않았습니다.

알고리즘은 아래와 같습니다.

1. 박스의 배치는 크게 두 가지로 나뉠 수 있습니다.

i) 일렬

ii) 두개 밑에 위에 하나

2. 가로와 세로를 입력 받을 때 90도 회전했을 때의 길이도 저장합니다.

3. 1번에서 말했던 두 가지 경우의 수로 나누어 모든 가능한 크기를 구하고 그 중 최소를 출력해줍니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int INF = 987654321;

 

int width[6], height[6];

 

int minBoxArea(void)

{

        int result = INF;

        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;

 

                                 //일렬

                                 int row = width[i] + width[j] + width[k];

                                 int col = max({ height[i], height[j], height[k] });

                                 result = min(result, row*col);

 

                                 //2개 1개

                                 row = max(width[i] + width[j], width[k]);

                                 col = max(height[i], height[j]) + height[k];

                                 result = min(result, row*col);

                         }

 

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int T;

        cin >> T;

 

        for (int t = 0; t < T; t++)

        {

                 for (int i = 0; i < 3; i++)

                 {

                         cin >> width[i] >> height[i];

                         //회전까지 입력

                         width[i + 3] = height[i];

                         height[i + 3] = width[i];

                 }

 

                 cout << minBoxArea() << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~