[프로그래머스] Lv.1 최소직사각형 c++

https://school.programmers.co.kr/learn/courses/30/lessons/86491?language=cpp

프로그래머스

 

다양한 크기의 명함을 모두 수납할 수 있는 최소 크기의 지갑을 만들어야 합니다.

• 명함은 가로와 세로를 자유롭게 회전할 수 있습니다.
• 모든 명함을 수납하려면 지갑의 가로 길이는 명함 중 가로와 세로 중 큰 값의 최댓값이 되어야 하고, 지갑의 세로 길이는 작은 값의 최댓값이 되어야 합니다.
• 최소 지갑 크기는 가로 최댓값 × 세로 최댓값으로 계산됩니다.

 

풀이 방법

이 문제는 완전탐색으로 해결할 수 있습니다.

명함은 가로와 세로를 자유롭게 회전할 수 있으므로, 각 명함의 가로와 세로가 고정되지 않아 조건을 판단하기 어려울 수 있습니다.
따라서 명함의 가로와 세로 중 더 긴 쪽을 가로로 고정하면, 회전에 대한 고민 없이 문제를 쉽게 풀 수 있습니다.

1. 각 명함의 가로와 세로를 비교하여 더 긴 값을 가로로, 짧은 값을 세로로 고정합니다.
2. 모든 명함에 대해 가로와 세로의 최댓값을 찾습니다.
3. 최댓값을 곱한 값이 지갑의 최소 크기가 됩니다.

이 방식으로 간단히 명함의 크기를 비교하여 조건을 만족하는 지갑 크기를 구할 수 있습니다.

 

풀이 코드

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

using namespace std;

int max_width, max_height;
int solution(vector<vector<int>> sizes) {
    int answer = 0;
    for(int i=0; i<sizes.size(); i++){
        if(sizes[i][0] < sizes[i][1]) swap(sizes[i][0],sizes[i][1]);
        if(max_width < sizes[i][0]) max_width = sizes[i][0];
        if(max_height < sizes[i][1]) max_height = sizes[i][1];
    }
    return max_width*max_height;
}

papago is broken