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

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

프로그래머스

 

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> sizes) {
    int answer = 0;
    int w=1001,h=1001;
    for(int i=0;i<sizes.size();i++)
    {
        if(sizes[i][0]<sizes[i][1])
        {
            int k=sizes[i][0];
            sizes[i][0]=sizes[i][1];
            sizes[i][1]=k;
        }
    }
    w=sizes[0][0];
    h=sizes[0][1];
    for(int i=1;i<sizes.size();i++)
    {
        if(w<sizes[i][0])
            w=sizes[i][0];
        if(h<sizes[i][1])
            h=sizes[i][1];
    }
    return h*w;
}

 

최소직사각형 문제는 모든 명함을 수납할 수 있는 가장 작은 수납함의 크기를 계산하는 문제이다.

명함은 회전시켜서 수납할 수 있다. 

2차원 벡터로 각 명함의 가로 세로 크기가 주어지는데 재귀함수가 아닌 반복문으로 해결하려고 해보았다.

 

명함은 회전시켜 수납이 가능하기 때문에 가로 세로 중 항상 가로가 더 길이가 길다고 가정하였다. 

따라서 첫 반복문처럼 세로가 더 길다면 스왑하였다.

 

이 가정을 통해 문제가 간단해진다. 

각 가로와 세로의 길이 중 가장 긴 길이가 모든 명함을 수납가능한 최소한의 크기이기 때문이다. 

 

두 번째 반복문을 통해서 가로,세로길이를 구하고 답을 도출한다.