프로그래머스 최소직사각형 C++

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

using namespace std;

int solution(vector<vector<int>> sizes) {
    int answer = 0;
    int height=0, width=0;
    for (int i=0;i<sizes.size();i++){
        if (sizes[i][0] > sizes[i][1]){
            height = max(height, sizes[i][0]);
            width = max(width, sizes[i][1]);
        }
        else{
            height = max(height, sizes[i][1]);
            width = max(width, sizes[i][0]);
        }
    }
    answer = height * width;
    return answer;
}

 

문제는 완전탐색 문제이다. 

결국, 최소 직사각형을 구하면 한쪽에 max값을 두고 다른쪽에 나머지를 두는 것이 가장 작다.

a+b=30일 때 a*b가 최소가 되게 만들려면 a=1, b=29가 가장 적은 값이다. 

a=15, b=15 이런식으로 하면 최대값이 된다.

 

따라서 for문을 돌면서 가로나 세로 중 한쪽에 가로와 세로 중 더 큰 값을 몰아줘서 갱신해주면 된다. 

더 큰 값이 담겼다는 것은 즉가로, 세로가 뒤집힌 것이다.