[C++] 최소직사각형

[문제]

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

프로그래머스

---

[문제 풀이]

생각보다 까다로웠던 문제였다.

완전 탐색 유형인데 어떤걸 가져와야 하는지 처음에는 감이 잘 안왔다가 블로그들을 보고 알게 되었다.

 

우리가 구할 값은 모든걸 통틀어서 가장 긴 변과 가장 짧은 변 중에서 가장 긴 변을 곱한 값이다.

전자는 쉽게 생각이 되었지만 후자를 생각하는 것이 쉽지 않았던 문제.

그럼 이제 어떻게 가장 짧은 변 중에서 가장 긴 변을 구하는지에 관해서 접근을 해보자.

구할 값 =  max(구할 값, min(가로길이, 세로길이))

해당 방식을 보면 어느정도 감이 왔을 것이다.

가로길이와 세로길이 중에서 짧은 길이를 min을 통해 구하고 해당 길이를 구할 값에서의 max로 스스로 비교하면서 계속 변경해주자.

---

[코드]

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

using namespace std;

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