프로그래머스 86491 - 최소직사각형 (Lv.1)

출처: https://school.programmers.co.kr/learn/courses/30/lessons/86491

// 프로그래머스 86491 - 최소직사각형 (Lv.1)
// https://school.programmers.co.kr/learn/courses/30/lessons/86491

// 문제 설명
// 명함 크기 [w, h]의 배열 sizes가 주어진다. 명함은 회전시킬 수 있고,
// 지갑 크기는 "가장 긴 가로 x 가장 긴 세로"로 결정된다.
// 모든 명함을 수납할 수 있는 최소 크기 지갑의 넓이를 반환하라.

// 제약 조건
// 1 <= sizes 길이 <= 10,000
// 각 원소는 [w, h], 1 <= w, h <= 1,000 인 자연수

// Example
// Input : [[60,50],[30,70],[60,30],[80,40]]
// Output: 4000   (긴 변 최댓값 80 x 짧은 변 최댓값 50)
//
// Input : [[10,7],[12,3],[8,15],[14,7],[5,15]]
// Output: 120    (15 x 8)
//
// Input : [[14,4],[19,6],[6,16],[18,7],[7,11]]
// Output: 133    (19 x 7)

// 접근 — 회전을 (긴 변, 짧은 변)으로 정규화하면 두 축이 독립
// 회전은 명함마다 독립으로 고를 수 있고 지갑은 max(가로) x max(세로)다.
// 어떤 명함의 긴 변을 세로로 돌리면 세로 최댓값만 커지거나 그대로이므로(교환 논증)
// 모든 명함의 긴 변을 같은 축으로 몰아주는 선택이 항상 최적이다.
// 1) 명함마다 max(w,h) = 긴 변, min(w,h) = 짧은 변으로 정규화한다.
// 2) 긴 변의 최댓값과 짧은 변의 최댓값을 각각 따로 갱신한다.
// 3) 두 최댓값의 곱이 답. 정렬도 조합 탐색도 필요 없다.
// 시간 O(n), 공간 O(1). 넓이 상한 1000 x 1000 = 1,000,000이라 int로 충분

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> sizes) {
    int maxLong = 0, maxShort = 0;                              // 긴 변 / 짧은 변 각각의 최댓값

    for (auto& s : sizes) {                                     // 인덱스가 필요 없으므로 범위 기반 for
        maxLong = max(maxLong, max(s[0], s[1]));                // 회전해서 긴 변을 한 축으로 몰아준다
        maxShort = max(maxShort, min(s[0], s[1]));              // 남은 짧은 변은 다른 축으로
    }

    return maxLong * maxShort;
}

정리

• 명함 하나마다 회전/비회전 두 갈래라 완전 탐색하면 2^10000이다. 그런데 정답은 O(n) 한 줄 루프다. 이 간극을 메우는 것이 “긴 변을 전부 같은 축으로 몰아주는 게 항상 최적“이라는 그리디 근거고, 이걸 못 세우면 왜 max(w,h)와 min(w,h)를 따로 모아도 되는지 설명할 수 없다.
• 교환 논증으로 보면 짧다. 어떤 명함 하나만 반대로 돌려 짧은 변을 가로 축에 놓는다고 하자. 가로 최댓값은 줄어들거나 그대로지만 세로 최댓값은 그만큼 늘어나거나 그대로다. 두 축의 최댓값은 서로 독립적으로 결정되고 한쪽을 줄이려면 다른 쪽에 더 큰 값을 밀어 넣어야 하므로, 곱이 작아지는 방향이 존재하지 않는다. 그래서 모든 명함을 같은 방향으로 정규화한 상태가 최적해다.
• 답은 “max들의 곱”이지 “곱들의 max”가 아니다. 예제 3에서 개별 명함의 최대 넓이는 18x7 = 126인데 답은 133이다. 긴 변 최댓값 19는 [19,6]에서, 짧은 변 최댓값 7은 [18,7]에서 나온다 — 두 축의 최댓값이 서로 다른 명함에서 나오고, 그 조합(19 x 7)에 해당하는 명함은 존재하지 않는다. 가장 큰 명함 하나를 찾는 문제로 착각하면 126을 답하게 되므로, 축별로 따로 모아야 한다.
• 정렬하고 싶은 충동이 드는 문제지만 필요 없다. 구하는 것이 최댓값 2개뿐이라 한 번 훑으며 갱신하면 끝 — 정렬은 O(n log n)에 순서 정보라는 필요 없는 것까지 계산한다. 2217 로프처럼 “정렬 후 스캔”이 필요한 그리디와 달리, 여기서는 후보 간 상호작용이 없어서 스캔만 남는다.
• 상한 점검: 최악이 10,000장이지만 답의 크기를 결정하는 건 변의 상한이다. 1000 x 1000 = 1,000,000으로 int(약 21억) 안에 넉넉히 들어간다. 곱셈 문제는 누적 상한부터 계산하고 자료형을 정한다는 42578·12949와 같은 습관.
• for (auto& s : sizes)로 참조 순회 — vector<int> 원소 10,000번 복사를 피한다. 값을 바꾸지 않으므로 const auto&가 더 정확하지만, 인덱스가 필요 없을 때 범위 기반 for를 쓰는 컨벤션은 그대로.
• 검증: 예제 3개(4000, 120, 133)와 상한 케이스(1000x1000 → 1,000,000) 통과 (MSVC /std:c++17 컴파일·실행).

핵심 요약 — 회전 선택은 명함마다 독립이고 지갑은 max(가로) x max(세로)이므로, 모든 명함을 (긴 변, 짧은 변)으로 정규화해 두 축의 최댓값을 따로 모아 곱하면 2^n 탐색이 O(n) 스캔으로 무너진다. 답은 “max들의 곱”이지 “가장 큰 명함의 넓이”가 아니다.