BOJ - 2304. 창고 다각형

문제

N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.

1. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
2. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
3. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
4. 지붕의 가장자리는 땅에 닿아야 한다.
5. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.

그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.

그림1 . 기둥과 지붕(굵은 선)의 예

창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.

기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.

입력

첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.

출력

첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.

사용할 자료구조

• 가장 긴 기둥을 기준으로 나누어 스택 두개를 사용하여 구현하였습니다.
• 기준 왼쪽은 left, 기준 오른쪽은 right으로 하여 각 스택의 top보다 큰 기둥만 담았습니다.

풀이 과정

1) 입력받은 순서대로 x,y값을 pair로 벡터 배열에 담으면서 가장 긴 기둥이 무엇인지 찾아줍니다.

가장 긴 기둥의 x값을 indexOfMaxHeight라 두고, 가장 긴 기둥의 길이를 maxHeight이라 저장해두었습니다,.

for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        if(maxHeight<y){
            maxHeight = y;
            indexOfMaxHeight = x;
        }
        v.push_back(make_pair(x,y));
    }

2) 현재 순서가 뒤죽박죽이므로, 문제에 나온 그림처럼 x값을 기준으로 정렬해줍니다.

3) 정렬이 끝났으면, 가장 긴 기둥을 기준으로 왼쪽 부분을 left스택에 담고, 오른쪽 부분을 right스택에 담아줍니다.

왼쪽 부분 : 0~가장 긴 기둥의 x좌표 -1

오른쪽 부분 : 가장 긴 기둥의 x좌표 + 1~ v.size()-1

(이 때, 스택의 top보다 더 긴 기둥만 스택에 삽입해줘야합니다.)

4) 스택에 다 담았으면, 각각 스택top값을 통해 x좌표와 높이를 뽑아내 넓이를 계산해주면됩니다.

시간 복잡도

• 스택의 삽입/삭제 연산 O(1) 만큼의 시간 복잡도를 가집니다. 총 네 번의 for문을 돌면서 N만큼 반복하므로 시간 복잡도는 4O(N) ⇒ *O(N)** 입니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    stack<pair<int,int>> left;
    stack<pair<int,int>> right;
    vector<pair<int,int>> v;
    int maxHeight=0;
    int indexOfMaxHeight=0;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        if(maxHeight<y){
            maxHeight = y;
            indexOfMaxHeight = x;
        }
        v.push_back(make_pair(x,y));
    }
    sort(v.begin(),v.end());
    int index;
    for(int i=0;i<v.size();i++){
        if(v[i].second==maxHeight && v[i].first==indexOfMaxHeight){
            index = i;
        }
    }

    for(int i=0;i<index;i++){
        if(right.empty()){
            right.push(make_pair(v[i].first,v[i].second));
        }else{
            if(right.top().second < v[i].second){
                right.push(make_pair(v[i].first,v[i].second));
            }
        }
    }

    for(int i=v.size()-1;i>index;i--){
        if(left.empty()){
            left.push(make_pair(v[i].first,v[i].second));
        }else{
            if(left.top().second < v[i].second){
                left.push(make_pair(v[i].first,v[i].second));
            }
        }
    }

    int answer = 1*maxHeight;
    int temp = indexOfMaxHeight;
    while(!right.empty()){
        answer = answer + right.top().second*(temp-right.top().first);
        temp=right.top().first;
        right.pop();
    }
    int temp2 = indexOfMaxHeight + 1;
    while(!left.empty()){
        answer = answer + left.top().second*(left.top().first+1-temp2);
        temp2 = left.top().first+1;
        left.pop();
    }
    cout<<answer;

    return 0;

}