[Algorithm] C++ 백준 8155번: Postering

문제: BOJ 8155 - Postering

서로 붙어 있는 건물들의 북쪽 면을 겹치지 않는 직사각형 포스터로 완전히 덮을 때, 필요한 최소 포스터 개수를 구하는 문제다.
핵심은 “폭(d)은 무시해도 되고, 높이 변화만 보면 된다”는 점이며, 답은 단조 스택(모노토닉 스택)으로 \(O(N)\)에 계산된다.

문제 정보

문제 링크: https://www.acmicpc.net/problem/8155

문제 요약:

• 동서로 일렬로 붙어 있는 \(n\)개의 건물이 있다.
• \(i\)번째 건물은 길이 \(d_i\), 높이 \(w_i\)를 가진다.
• 포스터는 직사각형이며 변은 수평/수직이고, 겹칠 수 없지만 맞닿는 것은 가능하다.
• 각 포스터는 연속된 일부 건물들의 벽에 완전히 붙어야 하며, 전체 북쪽 면이 덮여야 한다.
• 최소 포스터 개수를 출력한다.

제한 조건:

• 시간 제한: 1초
• 메모리 제한: 128MB
• \(1 \le n \le 250{,}000\)
• \(1 \le d_i, w_i \le 1{,}000{,}000{,}000\)

입출력 예제

입력 1:

1
2
3
4
5
6

5
1 2
1 3
2 2
2 5
1 4

출력 1:

1

4

접근 방식

핵심 관찰 1: “폭 \(d_i\)”는 정답에 영향이 없다

포스터는 항상 건물 벽에 붙어야 하고 수직/수평 변만 허용된다. 따라서 북쪽 면을 덮는 데 필요한 것은 동서 방향의 “길이” 자체가 아니라 높이의 변화(스카이라인의 형태)다.
건물 폭이 달라도 높이의 구간 배치는 동일한 높이 시퀀스를 “늘린 것”에 불과하므로, 최소 포스터 개수는 높이 배열 \(w_i\)만으로 결정된다.

핵심 관찰 2: 높이가 내려갈 때마다 “이제 끝난 포스터”가 생긴다

왼쪽에서 오른쪽으로 진행한다고 하자.

• 현재 높이가 더 커지면: 새로운 높이 영역을 덮기 위해 포스터가 “시작”될 수 있다.
• 현재 높이가 더 작아지면: 이전에 시작된 더 높은 포스터들은 이 지점에서 더 이상 진행할 수 없으므로 “종료”된다.

이 “종료되는 포스터 개수”를 정확히 세기 위해 단조 증가 스택을 사용한다.

알고리즘 (단조 스택)

스택에는 “현재까지 열린(진행 중인) 높이들”을 오름차순으로 유지한다. 맨 아래에는 센티넬 0을 둔다.

각 건물 높이 \(h\)에 대해:

• 스택 top이 \(h\)보다 크면, top 높이 포스터는 여기서 끝나므로 pop하고 카운트 +1 (top \(\le h\)가 될 때까지 반복)
• top이 \(h\)보다 작으면, 새로운 높이 포스터가 시작되므로 push(\(h\))
• top이 \(h\)와 같으면, 같은 높이는 이미 진행 중이므로 아무 것도 하지 않는다(중복 방지)

모든 건물을 처리한 뒤 스택에 남아 있는 \(>0\) 높이들은 오른쪽 끝에서 종료되므로 전부 pop하며 카운트한다.

알고리즘 설계 (Mermaid Flowchart)

flowchart TD
    A["입력 n 및 (d_i, w_i)"] --> B["스택 초기화: st=[0], ans=0"]
    B --> C["각 i에 대해 h=w_i 처리"]
    C --> D{"st.top > h ?"}
    D -->|"yes"| E["pop; ans++"] --> D
    D -->|"no"| F{"st.top < h ?"}
    F -->|"yes"| G["push(h)"] --> C
    F -->|"no"| H["(같은 높이) skip"] --> C
    C --> I["모든 i 처리 후 st.top>0 동안 pop; ans++"]
    I --> J["ans 출력"]

정당성 스케치

• 스택에는 현재까지 오른쪽으로 “열려 있는” 높이들이 중복 없이 오름차순으로 유지된다.
• 높이가 감소하는 순간, 그보다 큰 높이 영역은 더 이상 진행될 수 없으므로 반드시 그 지점에서 끝나야 하며, 이는 포스터 하나의 종료에 대응한다.
• 같은 높이는 이어붙일 수 있으므로(겹치지 않게 맞닿게 배치 가능) 중복 카운트를 방지하기 위해 “같으면 push하지 않는다”.
• 각 높이는 최대 1번 push되고 1번 pop되므로 전체는 상각 \(O(N)\)이다.

복잡도 분석

코너 케이스 및 실수 포인트

구현 코드

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

// 42jerrykim.github.io에서 더 많은 정보를 확인할 수 있다
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<long long> st;
    st.reserve(n + 1);
    st.push_back(0); // sentinel

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        long long d, h;
        cin >> d >> h; // d is irrelevant for counting posters; only height h matters

        while (st.back() > h) {
            st.pop_back();
            ans++;
        }
        if (st.back() < h) st.push_back(h);
    }

    while (st.back() > 0) {
        st.pop_back();
        ans++;
    }

    cout << ans << "\n";
    return 0;
}

참고 문헌 및 출처

• BOJ 8155 - Postering