[완전탐색]최소 직사각형

문제

 

모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다.
모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.

 

 

접근 방법

#1차

 

1) 출력 정의
 - 모든 명함을 수납 할 수 있는 가장 작은 지갑. 

2) 문제 정의
 - 모든 명함을 정렬 (앞 큰것, 뒤 작은것)으로. 
 - 해당 명함들의 가로 세로값의 최댓값 찾기.

 3) 구현
  - 명함 정렬 
   -> 큰값은 앞으로 작은값은 뒤로.
  - 가로의 max값과 세로의 max값으로 지갑 만들기.

 

코드

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

using namespace std;

int solution(vector<vector<int>> sizes) {
    int answer = 0;

    // 명함 정렬 큰값 앞, 작은 값 뒤.
    int width=0,length=0;

    for(auto vec : sizes)
    {
        if(vec[0]<vec[1])
            swap(vec[0],vec[1]);
        
        if(width<vec[0])
            width=vec[0];
        
        if(length<vec[1])
            length=vec[1];
    }

    answer = width*length;

    return answer;
}

 

#2차 (보완사항)

 

1) 출력 정의
 - 모든 명함을 수납 할 수 있는 가장 작은 지갑.

2) 문제 정의
 - 모든 명함을 정렬 (앞 큰것, 뒤 작은것)으로. 
 - 해당 명함들의 가로 세로값의 최댓값 찾기.

 

정렬할 필요 없음.
명함 배열의 값중 큰값을 너비, 작은 값을 높이로 구현

 

 3) 구현
  - width = 모든 명함의 max 값

  - length = 모든 명함의 min 값

 

코드

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

using namespace std;

int solution(vector<vector<int>> sizes) {
    int answer = 0;

    // 명함 정렬 큰값 앞, 작은 값 뒤.
    int width=0,length=0;

    // 명함의 긴값과 현재 값중 max인 값.
    for(auto vec : sizes)
    {
        width = max(width,max(vec[0],vec[1]));
        length = max(length,min(vec[0],vec[1]));
    }

    answer = width*length;

    return answer;
}

 

 

위의 문제가 왜 완전탐색 문제인가?

명함을 자유롭게 회전할 수 있기 때문에 가능한 모든 경우의 수를 따져야 하기 때문이다.

 

하지만, 위의 문제는 최적화된 문제의 풀이를 정의할 수 있기때문에 그리디 방식으로도 풀이가 가능하다.

최적화된 문제 풀이 정의 
- 명함의 긴 부분을 width로 고정시키는 방법

그리디 방식
 - 부분 문제의 해로 전체 문제를 해결 할 수 있는 방식

 

위의 방식은 그리디 방식으로 풀이한 결과이다.