[BOJ 백준] 2304번 창고 다각형

문제

BOJ 2304 : https://www.acmicpc.net/problem/2304

2304번: 창고 다각형

접근

주어진 기둥들을 모두 사용하여 지붕을 지을 때 가장 작은 창고 면적을 구하는 문제이다. 가장 주목해야 하는 조건은 비가 올 때 물이 고이지 않도록 어떤 부분도 오목하게 들어가서는 안 된다는 것이다.

먼저 지붕에 오목한 부분이 없도록 지으려면 지붕의 높이가 낮아졌다가 다시 높아지면 안 된다.(┗ ┛이런 모양새가 되므로 비가 오면 물이 고일 것이다.) 따라서 현재 기둥보다 더 높은 기둥을 만날 때만 지붕의 높이를 높여주면 된다.

하지만 이 방법대로 가다 보면 가장 높은 기둥을 만난 후부터는 가장 높은 기둥을 기준으로 지붕이 만들어지기 때문에 창고의 면적이 최소가 되지 못한다는 문제가 생긴다. 따라서 가장 마지막 index부터 가장 높은 기둥까지 다시 탐색해주어야 한다.

그러기 위해 기둥을 좌표 순서대로 sort한 뒤 0번째 index부터 마지막까지 순차적으로 탐색하면서 가장 높은 기둥의 왼쪽 부분의 면적을 구해주면 된다. 탐색을 마치면 가장 높은 기둥을 알 수 있기 때문에 마지막 index부터 가장 높은 기둥까지 역순으로 다시 탐색해 주면서 가장 높은 기둥의 오른쪽 부분의 면적을 구해나가면 된다.

코드

// algorithm study
// BOJ_2304_창고 다각형

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

using namespace std;

bool p_sort(pair<int, int> a, pair<int, int> b) {
    if (a.first == b.first)
        return a.first;
    return a.first < b.first;
}

int main() {
    int n, max_h = 0, max_x = 0, answer = 0;
    cin >> n;
    vector<pair<int, int>> arr;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        arr.push_back({a, b});
    }
    sort(arr.begin(), arr.end(), p_sort);
    for (int i = 0; i < n; i++) {
        if (arr[i].second >= max_h) {
            answer += (arr[i].first - max_x) * max_h;
            max_x = arr[i].first;
            max_h = arr[i].second;
        }
    }
    answer += max_h;
    int savex = max_x;
    max_h = max_x = 0;
    for (int i = n - 1; arr[i].first > savex; i--) {
        if (arr[i].second > max_h) {
            answer += (max_x - arr[i].first) * max_h;
            max_x = arr[i].first;
            max_h = arr[i].second;
        }
    }
    answer += (max_x - savex) * max_h;
    cout << answer;
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study