BOJ 2304 - 창고 다각형 링크
(2023.09.08 기준 S2)

문제

폭이 모두 1m인 N개의 막대 기둥이 일렬로 세워져 있다. 오목한 부분이 없게끔 기둥을 전부 포함하는 지붕을 만드려고 한다. 이를 옆에서 바라보았을 때, 면적이 최소한의 될 때의 면적 출력

알고리즘

기둥의 위치를 차례대로 훑으면서 스택을 이용하여 높이 저장 및 면적 구하기

풀이

기둥의 높이가 단조증가한다고 생각해보자.
지붕은 최소한의 면적을 이뤄야 하기 때문에, 더 높은 기둥이 나오기 전까진 현재 기둥의 높이를 유지하면서 쭉 이어지게 된다. 이 성질을 이용하여 왼쪽과 오른쪽에서 훑으면서 더 높은 기둥이 나올 때마다 stack에 push하고, 가장 높은 기둥을 제외한 양쪽 면적을 구하여 가장 높은 기둥의 높이를 더하면 된다.

문제 지문에 나온 예시다.
어차피 가장 높은 기둥의 높이는 같기 때문에, 양쪽에서 훑었을 때의 가장 높은 기둥. 즉, 마지막 기둥은 동일하다.
그러므로, 위와 같이 구하면 된다.

이 때, 주의해야 할 점이 있다.

위와 같이 가장 높은 높이를 가진 기둥이 여러 개일 수 있다. 그러니 왼쪽이나 오른쪽 둘 중 한 쪽에선 같은 경우에도 stack에 push해야 한다.

코드

• C++

#include <bits/stdc++.h>
#define l first
#define h second
using namespace std;

typedef pair<int, int> pii;

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

    int N; cin >> N;
    vector<pii> P(N); for (int i = 0; i < N; i++) cin >> P[i].l >> P[i].h;
    sort(P.begin(), P.end()); // 위치 순으로 기둥을 정렬

    // 왼쪽에서부터 훑기
    stack<int> stk; stk.push(0);
    for (int i = 1; i < N; i++)
        if (P[stk.top()].h < P[i].h) // 마지막 기둥보다 높이가 더 높으면 넣기
            stk.push(i);

    // 가장 높은 기둥의 높이 × 1
    int result = P[stk.top()].h;

    // 가장 높은 기둥 직전까지의 왼쪽 면 넓이
    int prev = P[stk.top()].l; stk.pop(); // 직전 기둥의 위치
    while (!stk.empty()){
        int i = stk.top(); stk.pop();
        result += (prev - P[i].l) * P[i].h;
        prev = P[i].l;
    }

    // 오른쪽에서부터 훑기
    stk.push(N - 1);
    for (int i = N - 2; i >= 0; i--)
        if (P[stk.top()].h <= P[i].h) // 마지막 기둥보다 높이가 더 높거나 같으면 넣기
            stk.push(i);

    // 가장 높은 기둥 직전까지의 왼쪽 면 넓이
    prev = P[stk.top()].l; stk.pop(); // 직전 기둥의 위치
    while (!stk.empty()){
        int i = stk.top(); stk.pop();
        result += (P[i].l - prev) * P[i].h;
        prev = P[i].l;
    }

    cout << result;
}

• Python

import sys; input = sys.stdin.readline

N = int(input())
P = sorted(tuple(map(int, input().split())) for _ in range(N)) # 위치 순으로 기둥을 정렬

# 왼쪽에서부터 훑기
stk = [0]
for i in range(1, N):
    if P[stk[-1]][1] < P[i][1]: # 마지막 기둥보다 높이가 더 높으면 넣기
        stk.append(i)

# 가장 높은 기둥의 높이 × 1
result = P[stk[-1]][1]

# 가장 높은 기둥 직전까지의 왼쪽 면 넓이
prev = P[stk.pop()][0] # 직전 기둥의 위치
while stk:
    i = stk.pop()
    result += (prev - P[i][0]) * P[i][1]
    prev = P[i][0]

# 오른쪽에서부터 훑기
stk = [N - 1]
for i in range(N - 2, -1, -1):
    if P[stk[-1]][1] <= P[i][1]: # 마지막 기둥보다 높이가 더 높거나 같으면 넣기
        stk.append(i)

# 가장 높은 기둥 직전까지의 오른쪽 면 넓이
prev = P[stk.pop()][0] # 직전 기둥의 위치
while stk:
    i = stk.pop()
    result += (P[i][0] - prev) * P[i][1]
    prev = P[i][0]

print(result)