[프로그래머스 고득점 kit] 최소 직사각형 (C++)

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

프로그래머스

위 문제에 대한 풀이입니다.

포인트는 어렵게 생각하지 않고, 첫번째 들어온 사각형을 고정해놓고,

그에 대해 선형 탐색을 통해 각 명함을 뒤집을 때와 그대로 둘 때를 비교하면 끝입니다.

#include <string>
#include <vector>
#include<algorithm>
#include<queue>
#include<iostream>
using namespace std;
bool compare(vector<int> a,vector<int> b){
    return a[1]<b[1];
}

int max(int a,int b){
    return a>b ? a:b;
}
priority_queue<pair<int,int>> origin;  //w 내린차순
priority_queue<pair<int,int>> rev; //h 내림차순
int solution(vector<vector<int>> sizes) {
    int answer = 0;
    int n=sizes.size();
    int max_w=sizes[0][0],max_h=sizes[0][1];
    answer=max_w*max_h;
    for(int i=1;i<sizes.size();i++){
        int w=sizes[i][0],h=sizes[i][1];
        int origin=max(w,max_w)*max(h,max_h),rev= max(w,max_h)*max(h,max_w);
        
        if(origin<=rev){ //해당 명함을 그대로 두는경우 넓이
            max_w=max(w,max_w);
            max_h=max(h,max_h);
            answer=origin;
        }
        else{  //해당 명함을 뒤집는 경우 넓이
            max_w=max(h,max_w);
            max_h=max(w,max_h);
            answer=rev;
        }
        
    }

    return answer;
}

 

+

다른 풀이로, 사각형의 한쪽 변을 최대, 남은 한쪽 변을 최소로 만들어서 해결하는 풀이도 있었습니다.