[프로그래머스] 86491번 - 최소직사각형 (완전탐색)

1. 문제 및 예제

 

 완전탐색이라고 그냥 너무 무식하게 다 비교하면 안된다는걸 알게된 문제. 처음에는 모든 높이와 넓이를 매칭시키고(여기서 나온 시간복잡도는 O(N*N) 이걸 모든 명함과 비교하는 방법.(결과적으로 총 시간 복잡도는 O(N*N*N)... 내가 미친거지 아주) 생각해보면 참 답이 없다 싶었다... 아직도 이런 문제로 해매다니... 자괴감 들었지만 그래도 다른 풀이들 참고하면서 풀었다. 개인적인 의견으로 수학 못 하는 나에게 이 문제는 레벨1 문제는 아닌듯...

---

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

프로그래머스

---

2. 풀이과정

 

 풀이과정은 간단하다. 높이와 넓이 중 최대 값을 구하면 된다. 다만 카드를 돌릴 수 있으므로 높이와 넓이를 일정하게 해주는 것이 중요. 나는 카드의 두 수 중에서 큰게 높이 작은게 넓이로 하기로 했다. 조금 더 구체적인 예를 들어보자. 다음은 입력된 값들이다.

---

---

 자 뒤죽박준인 저 값들을 다음과 같이 높은 숫자를 앞에 적은 숫자를 뒤에 오도록 정렬할 것이다. 그럼 다음과 같은 결과가 나온다.

---

---

 자 그럼 각 열에서 가장 큰 값만 뽑아오면 정답이다. 1열은 80, 2열은 50이 될것이다. 둘이 곲하면 정답인 4000이 나온다.

 

3. 소스 코드

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

using namespace std;

int solution(vector<vector<int>> sizes) {
    int answer;
    int height = 0;
    int weight = 0;
    
    for(auto size : sizes){
        if(size[0] > size[1]){
            height = max(size[0] , height);
            weight = max(size[1] , weight);
        }else{
            height = max(size[1], height);
            weight = max(size[0], weight);
        }
    }
    
    return height * weight;
}