[C++/Programmers] Lv1. 최소직사각형

코딩테스트 연습도 하면서 이것도 기록하게 되면 좋을 것 같아 이제부터 기록하려 한다..

 

어떻게 풀어냈었는지, 어떻게 접근하는지에 중점을 둘 계획이다.

 

---

최소 직사각형

문제

레벨 1의 문제인데.. 접근을 잘못하게 되면 고생을 좀 하게 될 것이다.

 

가로 길이와 세로 길이라고 적어 놓은 것이 문제 풀이의 사고를 딱딱하게 만들어 주는 주 요인이라고 생각한다..

 

처음에 내가 생각했던 것은 가로 길이와 세로 길이를 따로 벡터에 저장 해 두고, 가장 큰 값을 회전시켜 넓이를 줄이는 것(..)으로 하였다.

 

그런데 완전 발상 자체가 틀렸었다..

 

문제에 나온 예시를 통해 보도록 하겠다..

 

문제 예시

ppt를 이용하여 실제 값을 주어 사이즈대로 그려 보았다.

실제 문제를 ppt를 통해 같은 사이즈로 그려 보았다

모서리를 왼쪽 아래로 맞추어 주게 되면 위 그림과 같은 상태가 되게 된다.

 

여기서 넓이가 줄어들기 위해서는 곱해지는 두 수가 모두 작아져야 한다.

 

두 개의 수를 모두 줄이기 힘들면 한 개의 수라도 최대한 작게 해 주어야 한다.

 

예를 들어서 17 x 5(=85) 와 14 x 8(=112) 은 둘의 합은 17 + 5 = 14 + 8 = 22로 같지만 밸런스 있게 분배하여 곱하는 것이 더 큰 수가 나오게 됨을 보여 준다.

 

따라서  곱해서 작은 수가 나오게 하기 위해서는 길이가 긴 부분들을 한 쪽으로 몰아주면 되는 것이다.

 

이렇게 코드를 작성하게 되면 아래와 같다.

 

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

using namespace std;

int solution(vector<vector<int>> sizes) {
    int answer = 0;
    
    int min = 0;
    int imsi = 0;
    int x_max = 0;
    int y_max = 0;
    
    vector<int> x_size;
    vector<int> y_size;
    vector<int> areas;
    
    for(int i=0;i<sizes.size();i++){
        if(sizes[i][0] >= sizes[i][1]){
            x_size.push_back(sizes[i][0]);
            y_size.push_back(sizes[i][1]);
        }else{
            x_size.push_back(sizes[i][1]);
            y_size.push_back(sizes[i][0]);
        }
        
    }
    
    x_max = *max_element(x_size.begin(),x_size.end());
    y_max = *max_element(y_size.begin(),y_size.end());

    
    return x_max*y_max;
}