[BOJ 14727] 퍼즐 자르기

백준 문제 링크

🔍 문제 분석

본 문제는 히스토그램에서 가장 큰 사각형의 넓이를 찾는 대표적인 유형의 문제로써 다양한 알고리즘을 통해서 해결할 수 있다.

1. 분할 정복

• 본 문제를 해결하는 가장 쉬운 방법 중 하나는 분할 정복을 이용하는 것이다.
• 가장 큰 넓이의 사각형이 존재할 수 있는 구간은 셋 중 하나이다.
  1. 왼쪽 구간
  2. 오른쪽 구간
  3. 가운데를 포함하는 구간
• 먼저, 주어진 범위를 정확히 반으로 분할한다. 1번과 2번에 해당하는 구간은 재귀호출로 해결할 수 있다. 3번 구간은 가운데에서 시작하여 왼쪽과 오른쪽 중 높이가 더 높은쪽으로 범위를 확장해 나가면서 넓이를 계산하는 방식으로 해결할 수 있다(이 과정은 O(N)의 시간 복잡도를 소요한다).

2. 스택 활용

• 추후 추가 예정

💻 코드 구현

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0)

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using vll = vector<ll>;
using vpi = vector<pi>;

constexpr int MAX = 1e5;
constexpr int INF = 1e9 + 7;

int N, cnt = 0;
ll H[MAX];

ll solve(int l, int r) {
    if (l == r) return H[l];
    int mid = (l + r) / 2;
    ll ret = max(solve(l, mid), solve(mid + 1, r));
    int _l = mid, _r = mid + 1; 
    ll min_h = INF;
    while (l <= _l || _r <= r) {
        if (l > _l) {
            min_h = min(min_h, H[_r]);
            ret = max(ret, min_h * (_r - _l));
            ++_r;
        } else if (r < _r) {
            min_h = min(min_h, H[_l]);
            ret = max(ret, min_h * (_r - _l));
            --_l;
        } else if (H[_l] > H[_r]) {
            min_h = min(min_h, H[_l]);
            ret = max(ret, min_h * (_r - _l));
            --_l;
        } else {
            min_h = min(min_h, H[_r]);
            ret = max(ret, min_h * (_r - _l));
            ++_r;
        }
    }
    return ret;
}

int main() {
    fastio;

    cin >> N;
    for (int i = 0; i < N; ++i) cin >> H[i];
    cout << solve(0, N - 1);
}

📝 코드 설명

🔧 트러블 슈팅

• 분할 정복의 병합 단계에서 범위 바깥으로 나가지 않도록 주의한다.

📚 참고자료

유사문제

• BOJ-1725: 히스토그램
• BOJ-6549: 히스토그램에서 가장 큰 직사각형