(완전탐색)최소직사각형

제한사항

• sizes의 길이는 1 이상 10,000 이하입니다.
• sizes의 원소는 [w, h] 형식입니다.
• w는 명함의 가로 길이를 나타냅니다.
• h는 명함의 세로 길이를 나타냅니다.
• w와 h는 1 이상 1,000 이하인 자연수입니다.

풀이

• 만들수 있는 모든 경우의 명함 크기를 담을 수 있어야 하기 때문에 최댓값을 찾는 과정 필요
• 명함1개당 가로, 세로 위치를 바꿀수 있는 2개의 경우가 나옴
• 테스트케이스 1번의 경우 4개의 명함에서 총 16가지의 명함크기가 나올 수 있다
• 가장큰 가로와 가장큰 세로를 곱했을 때 최소를 구해야하기 때문에 가로나 세로중 하나를 정해서 작은 값을 모으고 한쪽은 큰값을 모아 그중에 최대값을 곱한다

#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int> col;
vector<int> row;
int solution(vector<vector<int>> sizes) {
    int answer = 0;
    //두값중 max값 한 벡터에 저장

    //4값중 max값 두 벡터에 저장 후 곱
    int max_n;
    int min_n;
    for (vector<int> v : sizes) {
        max_n = *max_element(v.begin(), v.end());
        min_n = *min_element(v.begin(), v.end());
        col.push_back(max_n);
        row.push_back(min_n);
    }

    max_n = *max_element(col.begin(), col.end());
    min_n = *max_element(row.begin(), row.end());
    answer = max_n * min_n;

    return answer;
}

모든 경우의 명함크기를 출력해보면 16번인 것을 알 수 있지만 코드로는 4번만 반복하여 최대값과 최솟값을 각각 저장하여 모든 과정을 반복하지 않도록 코드를 짤 수 있다.