최소직사각형

들어가는 말

여러 크기의 명함이 주어졌을 때, 모든 명함이 들어가는 가장 작은 크기의 지갑을 찾는 문제이다. 이차원 벡터로 가로와 세로가 주어지는데 가로와 세로를 나눠서 생각하면 곤란하다. 열을 기준으로 긴 것을 가로로 두고 나머지 것을 세로로 둬서, 둘 중에 제일 긴 것을 고르면 된다.

코드 설명

열을 기준으로 v(가로)를 긴 것으로 h(세로)를 작은 것으로 둔다. 다음 두 숫자 중 제일 큰 것을 골라주면 된다.
가로와 세로를 나눠서 봐서 문제 푸는 데 시간이 걸렸다. 가로와 세로 중 무엇이 큰 건지를 보는 게 아니라, 둘 중에 긴 것을 가로로 작은 것을 세로로 둬야 한다. 즉, 가로를 중심으로 명함들을 쌓는 다고 생각하면 편하다.

코드

#include <string>
#include <vector>
#include<algorithm>

using namespace std;

int solution(vector<vector<int>> sizes) {
    int h = 0;
    int v = 0;
    int max_h = 0;
    int max_v = 0;
    
    for(int i=0; i<sizes.size(); i++){
        v = max(sizes[i][0], sizes[i][1]);
        h = min(sizes[i][0], sizes[i][1]);
        
        max_v = max(max_v, v);
        max_h = max(max_h, h);
    }
    
    return max_v * max_h;
}

참고

초반에는 도저히 모르겠어서 이 블로그 풀이를 참고했다. 제출을 한 후 몇 분 더 고민해서 원리를 알았다는 건 안 비밀.
https://taehoung0102.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%EC%9E%90%EB%B0%94-Level1-%EC%B5%9C%EC%86%8C%EC%A7%81%EC%82%AC%EA%B0%81%ED%98%95-%EC%9C%84%ED%81%B4%EB%A6%AC-8%EC%A3%BC%EC%B0%A8