n쌍의 상자를 정사각형 모양의 컨테이너에 실어 보내야 한다고 가정해 봅시다. 각 상자 쌍의 크기는 (a, b) 형태의 순서쌍으로 주어지며, 이 값들은 dimensions 배열에 담겨 있습니다. 상자들을 위로 쌓을 수는 없고, 나란히 배치해야 할 때 각 쌍의 상자가 컨테이너 안에서 차지하게 되는 면적을 구하는 것이 우리의 과제입니다.
여기서 핵심은 두 상자를 긴 변을 세로로 세워 나란히 놓으면, 컨테이너의 높이는 max(a, b)가 되고 전체 폭은 2 × min(a, b)가 된다는 점입니다. 정사각형 컨테이너의 한 변의 길이는 이 두 값 중 더 큰 값 이상이어야 하므로, 필요한 최소 한 변의 길이는 다음과 같이 계산됩니다.
side = max(2 * min(a, b), max(a, b))
최종적으로 요구되는 면적은 이 한 변의 길이를 제곱한 값, 즉 side × side입니다.
입력 예시
예를 들어 n = 4이고 dimensions = {{2, 4}, {3, 6}, {2, 5}, {4, 6}}이라면, 출력은 다음과 같습니다.
64 25 36 16
풀이 단계
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 결과를 저장할 변수 res를 0으로 초기화합니다.
- n이 0이 될 때까지 반복하면서 각 순서쌍의 첫 번째 값을 a, 두 번째 값을 b로 가져옵니다.
- res를 max(2 × min(a, b), max(a, b))로 계산합니다.
- res의 제곱 값을 출력합니다.
- n을 하나 감소시키며 모든 쌍에 대해 반복합니다.
C++ 구현 예제
아래 구현을 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int n, vector<pair<int, int>> dimensions) {
int res = 0;
while(n--){
int a = dimensions[n].first;
int b = dimensions[n].second;
int res = max(2 * min(a, b), max(a, b));
cout<< res * res << endl;
}
}
int main() {
int n = 4;
vector<pair<int, int>> dimensions = {{2, 4}, {3, 6}, {2, 5}, {4, 6}};
solve(n, dimensions);
return 0;
}실행 결과
위 코드를 실행하면 아래와 같은 결과를 얻을 수 있습니다.
64 25 36 16
핵심 정리
이 알고리즘은 각 상자 쌍에 대해 O(1)의 시간 복잡도로 최소 면적을 계산하므로, 전체 시간 복잡도는 O(n)입니다. min과 max 함수만으로 간단히 해결되는 직관적인 기하 문제로, 상자 배치 방식에 따라 필요한 컨테이너 크기가 어떻게 달라지는지 이해하는 것이 핵심입니다.