BOJ 11861 - Maximal Area 링크
(2024.04.02 기준 P5)

문제

일직선의 길과 그 위로 $N$개의 열이 있다. 그리고 $i$번 열에는 $D_i$개의 정사각형이 가장 아래쪽부터 분할되어 있다.

여러 개의 정사각형으로 구성될 수 있는 최대 직사각형의 표면 출력

알고리즘

분할 정복 + 세그먼트 트리 or 스택

풀이

히스토그램 문제와 동일하다. $N$이 좀 커졌을 뿐.

히스토그램의 풀이는 두 가지가 있는데, 두 풀이에 공통적으로 쓰이는 핵심은 $i$번 열이 포함되는, $D_i$ 높이의 최대 직사각형을 구하는 것이다.

1. 분할 정복 + 세그먼트 트리

$f(h)$를 높이 $h$일 때의 최대 직사각형의 너비라고 정의하자. 직사각형의 높이가 낮을수록 너비는 커진다. 이를 이용해보자.

너비가 가장 넓은 $[0, N-1]$ 구간에서 가장 높이가 낮은 열의 인덱스 $m$을 구해보자. 높이 $D_m$은 $[0, N-1]$ 구간의 모든 열이 다 포함을 할 수 있으므로, $[0, N-1]$ 구간에서의 높이 $D_m$을 가지는 최대 직사각형의 넓이는 $D_m \times N$이 된다.

이제 $D_m$보다 높은 높이를 가지는 직사각형들을 구해야 한다. 이는 $m$번 열이 포함될 수 있을까? 불가능하다. 그러므로 이제 $[0, m-1]$ 구간과 $[m+1, N-1]$ 구간을 살펴봐야 한다.

이런 식으로 구간을 분할하면서 값을 구하면 된다. 이때, 특정 구간에서의 값은 세그먼트 트리를 이용하면 된다.

2. 스택

각 열마다 그 열이 완전히 포함된 최대 직사각형을 구할 것이다. 스택에 첫 번째 열부터 하나씩 쌓아보자.
각 스택에 쌓여진 열은 높이가 자기만큼인 직사각형이 오른쪽으로 최대한 이어간다고 생각하자. 스택의 마지막 높이보다 쌓고자 하는 높이가 같거나 높다면 직사각형은 계속 이어지지만, 쌓고자 하는 높이가 더 낮다면 직사각형은 끊어진다. 그럼 그 끊어지는 곳까지의 넓이를 구해 정답을 갱신하면 된다.

현재 쌓고자 하는 열의 인덱스는 $i$, $j$가 스택에서 pop되어 값을 구해야 할 때, 현재 스택의 top을 $k$라고 하자. 그러면 $[k+1, i-1]$ 구간의 모든 열의 높이는 $D_j$보다 같거나 높다. 즉, $j$번 열이 완전히 포함되는 최대 직사각형은 $[k+1, i-1]$ 구간을 덮으며 높이 $D_j$를 가지게 된다.

위 과정을 모든 $i$에 대해 순서대로 거치면, 스택에 남는 인덱스들은 높이가 비내림차순을 이루게 된다. 그러면 남아있는 열들에 대해서, 각 열을 포함하는 직사각형은 자기보다 일찍 스택에 담긴 열 중 가장 마지막 열 이후부터 끝까지 직사각형을 이루게 된다.

코드

분할 정복 + 세그먼트 트리

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1'000'000, MAXM = 1 << (int)ceil(log2(MAXN) + 1);

int N, D[MAXN], T[MAXM];

// 더 작은 값을 가지는 인덱스 반환
int merge(int l, int r){
    if (!~l) return r;
    if (!~r) return l;
    if (D[l] <= D[r]) return l;
    return r;
}

// 세그먼트 트리 구축
void init(int nd, int st, int en){
    if (st == en){
        T[nd] = st;
        return;
    }
    int mid = (st + en) >> 1;
    init(nd << 1, st, mid);
    init(nd << 1 | 1, mid + 1, en);
    T[nd] = merge(T[nd << 1], T[nd << 1 | 1]);
}

// [l, r] 쿼리
int query(int nd, int st, int en, int l, int r){
    if (r < st || en < l) return -1;
    if (l <= st && en <= r) return T[nd];
    int mid = (st + en) >> 1;
    return merge(query(nd << 1, st, mid, l, r), query(nd << 1 | 1, mid + 1, en, l, r));
}

// 분할 정복
ll dnc(int l, int r){

    // 하나의 열만 보고 있으면 그 열의 넓이는 D_l 값이 된다.
    if (l == r) return D[l];

    // [l, r] 구간에서 최솟값을 가지는 인덱스 mid를 찾는다.
    // 그리고 mid 열을 포함하는 최대 넓이를 구한다.
    int mid = query(1, 0, N - 1, l, r);
    ll res = (ll)D[mid] * (r - l + 1);

    // mid 열의 높이보다 더 높은 직사각형의 넓이를 찾아나선다.
    if (l < mid) res = max(res, dnc(l, mid - 1));
    if (mid < r) res = max(res, dnc(mid + 1, r));

    return res;
}

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

    cin >> N;
    for (int i = 0; i < N; i++) cin >> D[i];

    int x = -1;

    init(1, 0, N - 1);

    cout << dnc(0, N - 1);
}

• Python (PyPy3)

import sys; input = sys.stdin.readline
from math import ceil, log2

# 더 작은 값을 가지는 인덱스 반환
def merge(l, r):
    if not ~l:
        return r
    if not ~r:
        return l
    if D[l] <= D[r]:
        return l
    return r

# 세그먼트 트리 구축
def init(nd, st, en):
    if st == en:
        T[nd] = st
        return
    mid = (st + en) >> 1
    init(nd << 1, st, mid)
    init(nd << 1 | 1, mid + 1, en)
    T[nd] = merge(T[nd << 1], T[nd << 1 | 1])

# [l, r] 쿼리
def query(nd, st, en, l, r):
    if r < st or en < l:
        return -1
    if l <= st and en <= r:
        return T[nd]
    mid = (st + en) >> 1
    return merge(query(nd << 1, st, mid, l, r), query(nd << 1 | 1, mid + 1, en, l, r))

# 분할 정복
def dnc(l, r):

    # 하나의 열만 보고 있으면 그 열의 넓이는 D_l 값이 된다.
    if l == r:
        return D[l]

    # [l, r] 구간에서 최솟값을 가지는 인덱스 mid를 찾는다.
    # 그리고 mid 열을 포함하는 최대 넓이를 구한다.
    mid = query(1, 0, N - 1, l, r)
    res = D[mid] * (r - l + 1)

    # mid 열의 높이보다 더 높은 직사각형의 넓이를 찾아나선다.
    if l < mid:
        res = max(res, dnc(l, mid - 1))
    if mid < r:
        res = max(res, dnc(mid + 1, r))

    return res

N = int(input())
D = list(map(int, input().split()))

T = [0] * (1 << ceil(log2(N) + 1))
init(1, 0, N - 1)

print(dnc(0, N - 1))

스택

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

    int N; cin >> N;
    int D[N]; for (int i = 0; i < N; i++) cin >> D[i];

    /* 우리는 각 열이 온전히 포함된 최대 직사각형을 구할 것이다.
    스택에 첫 번째 열부터 하나씩 쌓아보자.
    각 스택에 쌓여진 열은 높이가 자기만큼인 직사각형이 오른쪽으로 최대한 이어간다고 생각하자.
    스택의 마지막 높이보다 쌓고자 하는 높이가 같거나 높다면 직사각형은 계속 이어지지만
    쌓고자 하는 높이가 더 낮다면 직사각형은 끊어진다.
    그럼 그 끊어지는 곳까지의 넓이를 구해 정답을 갱신하면 된다. */

    stack<int> stk; // 인덱스 저장
    ll ans = 0;
    for (int i = 0; i < N; i++){
        while (!stk.empty() && D[stk.top()] > D[i]){ // 쌓고자 하는 높이가 더 낮다면 직사각형은 끊어진다.
            int j = stk.top(); stk.pop();

            // j 열이 온전히 포함된 직사각형은 높이 D_j로
            // 자기보다 일찍 스택에 담겨 있는 열 중 가장 마지막 열 이후부터
            // 현재 인덱스 직전인 i-1까지 이어졌다.
            if (!stk.empty()) ans = max(ans, (ll)D[j] * (i - stk.top() - 1));
            // 남아있는 원소가 없다면 직사각형의 시작은 처음부터다.
            else ans = max(ans, (ll)D[j] * i);
        }

        stk.push(i);
    }

    /* 스택에 남아있는 열들은 높이가 비내림차순을 이룬다.
    그러면 각 열을 포함하는 직사각형은
    자기보다 일찍 스택에 담긴 열 중 가장 마지막 열 이후부터
    끝까지 직사각형을 이루게 된다. */

    while (!stk.empty()){
        int i = stk.top(); stk.pop();
        if (!stk.empty()) ans = max(ans, (ll)D[i] * (N - stk.top() - 1));
        // 더 이상 남아있는 원소가 없다면 자기 높이를 가지는 직사각형이 너비 N을 가진다는 뜻이다.
        else ans = max(ans, (ll)D[i] * N);
    }

    cout << ans;
}

• Python

import sys; input = sys.stdin.readline

N = int(input())
D = list(map(int, input().split()))

''' 우리는 각 열이 온전히 포함된 최대 직사각형을 구할 것이다.
스택에 첫 번째 열부터 하나씩 쌓아보자.
각 스택에 쌓여진 열은 높이가 자기만큼인 직사각형이 오른쪽으로 최대한 이어간다고 생각하자.
스택의 마지막 높이보다 쌓고자 하는 높이가 같거나 높다면 직사각형은 계속 이어지지만
쌓고자 하는 높이가 더 낮다면 직사각형은 끊어진다.
그럼 그 끊어지는 곳까지의 넓이를 구해 정답을 갱신하면 된다. '''

stk = [] # 인덱스 저장
ans = 0
for i in range(N):
    while stk and D[stk[-1]] > D[i]: # 쌓고자 하는 높이가 더 낮다면 직사각형은 끊어진다.
        j = stk.pop()

        # j 열이 온전히 포함된 직사각형은 높이 D_j로
        # 자기보다 일찍 스택에 담겨 있는 열 중 가장 마지막 열 이후부터
        # 현재 인덱스 직전인 i-1까지 이어졌다.
        if stk:
            ans = max(ans, D[j] * (i - stk[-1] - 1))
        else: # 남아있는 원소가 없다면 직사각형의 시작은 처음부터다.
            ans = max(ans, D[j] * i)

    stk.append(i)

''' 스택에 남아있는 열들은 높이가 비내림차순을 이룬다.
그러면 각 열을 포함하는 직사각형은
자기보다 일찍 스택에 담긴 열 중 가장 마지막 열 이후부터
끝까지 직사각형을 이루게 된다. '''

while stk:
    i = stk.pop()
    if stk:
        ans = max(ans, D[i] * (N - stk[-1] - 1))
    else: # 더 이상 남아있는 원소가 없다면 자기 높이를 가지는 직사각형이 너비 N을 가진다는 뜻이다.
        ans = max(ans, D[i] * N)

print(ans)