프로그래머스 최소직사각형 c++ // greedy?

https://school.programmers.co.kr/learn/courses/30/lessons/86491

프로그래머스

1. 문풀과정

분류가 완탐이라길래

가로선택-세로선택 분기로 알고리즘짬

-> 최악 : O(2^1000) -> 불가능

그리디로 풀이를 바꾸었다.

 

2. 전체코드

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> big,small;

int solution(vector<vector<int>> sizes) {
    int answer = 0;
    n=sizes.size();
    
    //큰것들모음 - big
    //작은것들 모음 - small
    for(auto v : sizes){
        if(v[0]>v[1]){
            big.push_back(v[0]);
            small.push_back(v[1]);
        }
        else{
            big.push_back(v[1]);
            small.push_back(v[0]);
        }
    }
    
    sort(big.begin(),big.end());
    sort(small.begin(),small.end());
    
    //큰것중 최대값 == 가로
    //작은것중 최대값 == 세로 로하면 최적해이다.
    
    return big[n-1]*small[n-1];
}