백준 2304 - 창고 다각형

 

 

문제 설명

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

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 주어진 기둥을 감싸는 지붕을 만들어 창고의 최소 면적을 구하는 것이다.

이때, 지붕은 가장 왼쪽과 오른쪽 기둥에 붙어 땅에 닿아야한다.

또한, 지붕에 오목한 부분이 없어야 한다.

 

이러한 조건을 간단히 하면 가장 왼쪽 혹은 오른쪽에 있는 기둥부터 시작하여 가장 높은 높이의 기둥까지 높이가 줄어들지 않은 채로 이동한 면적을 구하면 된다.

예를 들어, 2에 위치한 기둥을 시작으로 8까지 이동하는 경우를 생각해 보자.

2에 위치한 기둥은 높이가 4이고 그 오른쪽에 있는 4에 위치한 기둥은 높이가 6이다.

2에서 4까지는 높이가 4인 지붕을 만들고 6부터 높이가 6인 지붕을 만들면 최소 면적을 보장한다.

따라서, 최대 높이까지 이동하며 현재의 최대 높이와 이동거리를 곱해 면적을 계산하면 된다.

int ans = maxHeight;
{
    int currentHeight = columns.begin()->second;
    int prevLoc = columns.begin()->first;

    for (auto itr = ++columns.begin(); itr != columns.end() && itr->first <= maxLoc; itr++)
    {
        int loc = itr->first;
        int height = itr->second;

        ans += currentHeight * (loc - prevLoc);

        currentHeight = max(currentHeight, height);
        prevLoc = loc;
    }
}

가장 왼쪽 기둥은 이동거리가 없기 때문에 예외적으로 처음에 계산하였고 왼쪽에서 두 번째 위치한 기둥부터 for문을 통해 계산한 것이다.

 

반대쪽(오른쪽)도 마찬가지로 진행할 수 있다.

{
    int currentHeight = columns.rbegin()->second;
    int prevLoc = columns.rbegin()->first;

    for (auto itr = ++columns.rbegin(); itr != columns.rend() && itr->first >= maxLoc; itr++)
    {
        int loc = itr->first;
        int height = itr->second;

        ans += currentHeight * (prevLoc - loc);

        currentHeight = max(currentHeight, itr->second);
        prevLoc = loc;
    }
}

 

해당 문제를 풀면서 시간 초과가 발생하였는데 입력처리에 대해서 문제가 생긴 것이었다.

처음에는 map을 통해 해결하였는데 map에 요소를 넣으며 정렬이 이루어져 시간 초과가 발생하였다.

따라서, pair를 가지는 vector로 자료구조를 변경해 모든 입력이 종료된 후 정렬을 한 번만 진행하는 방식으로 바꾸어 해결하였다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>

using namespace std;

int N;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    
    vector<pair<int, int>> columns;
    int maxHeight = 0;
    int maxLoc = 0;

    for (int i = 0; i < N; i++)
    {
        int loc, height;
        cin >> loc >> height;

        columns.push_back({ loc, height });
        if (maxHeight < height)
        {
            maxHeight = height;
            maxLoc = loc;
        }
    }

    sort(columns.begin(), columns.end());

    int ans = maxHeight;
    //left
    {
        int currentHeight = columns.begin()->second;
        int prevLoc = columns.begin()->first;

        for (auto itr = ++columns.begin(); itr != columns.end() && itr->first <= maxLoc; itr++)
        {
            int loc = itr->first;
            int height = itr->second;

            ans += currentHeight * (loc - prevLoc);

            currentHeight = max(currentHeight, height);
            prevLoc = loc;
        }
    }
	
    //right
    {
        int currentHeight = columns.rbegin()->second;
        int prevLoc = columns.rbegin()->first;

        for (auto itr = ++columns.rbegin(); itr != columns.rend() && itr->first >= maxLoc; itr++)
        {
            int loc = itr->first;
            int height = itr->second;

            ans += currentHeight * (prevLoc - loc);

            currentHeight = max(currentHeight, itr->second);
            prevLoc = loc;
        }
    }

    cout << ans;

    return 0;
}

---