백준 28229번: Ammunition Storage [C++]

작성일 | In
플래티넘 II 플래티넘 II

문제

Ammunition Storage

랜덤 마라톤 H번에서 만난 문제입니다.

미친듯한 난이도에 엄청 고민했는데 에디토리얼이 없어서 선배의 도움을 받았습니다.

풀이

먼저 직사각형의 윗변과 아랫변을 고정합니다.

그러니까 위쪽 행($u$)와 아래쪽 행($d$)를 고정한 다음 열에 대해서만 고려해봅시다.

열에서 코너의 최솟값 $\mathrm{cornerMin}[c] = \min(g[u][c], g[d][c])$라 합시다.

코너를 제외한 열의 최댓값을 $\mathrm{innerMax}[c]$라 합시다.

코너를 포함한 열의 최댓값을 $\mathrm{totalMax}[c]$라 합시다.

우리는 직사각형을 구성할 수 있는 두 열을 찾아서 그러한 쌍의 개수를 세 줄 것입니다.

어떤 두 열 $c1$과 $c2$에 대해

  1. $\mathrm{cornerMin}[c1] < \mathrm{cornerMin}[c2]$인 경우 해당 직사각형은 오른쪽으로 확장할 수 없습니다. $\mathrm{cornerMin}[c1]$이 $\mathrm{totalMax}[c2]$보다 항상 작기 때문입니다.
  2. 마찬가지로 $\mathrm{cornerMin}[c1] > \mathrm{cornerMin}[c2]$인 경우 왼쪽으로 확장할 수 없습니다.

따라서 2번 경우를 만족하도록 단조 스택에 열을 넣고 잘 관리하면 문제를 해결할 수 있습니다.

$\mathrm{cornerMin}$이 감소하도록 인덱스를 가지고 있는 스택 $\mathrm{left}$에 대해 $\mathrm{left}[i]$가 왼쪽 변일 때 직사각형 내부의 최댓값 $\mathrm{rightMax}[i]$를 스택으로 관리합니다.

스택의 top을 $\mathrm{stackname}[top]$과 같이 쓰겠습니다.

$\mathrm{cornerMin}[\mathrm{left}[top]] < \mathrm{totalMax}[c]$인 경우 더 이상 $\mathrm{left}[top]$은 $c$보다 오른쪽의 열과 직사각형을 이룰 수 없습니다. 따라서 스택에서 pop합니다. 이때 $\mathrm{left}[top]$과 $c$가 직사각형을 이룰 수 있는지 체크하고, $\mathrm{rightMax}$도 업데이트 해 줍니다.

$\mathrm{left}[top]$이 왼쪽 변이고 $c$가 오른쪽 변인 경우 네 코너를 제외한 내부 최댓값은 $\max(\mathrm{rightMax}[top], \mathrm{innerMax}[c])$로 빠르게 구할 수 있습니다.

내부 최댓값보다 네 코너의 최솟값이 더 크다면 $top$과 $c$는 서로 직사각형을 이룰 수 있으므로 답에 $1$을 더해 줍니다.

코드

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(_) ((void)0)
#endif
using namespace std;

constexpr int LIMIT = 777;

int grid[LIMIT][LIMIT];
int cornerMin[LIMIT], totalMax[LIMIT], innerMax[LIMIT];

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

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    }

    int answer = 0;
    for (int u = 1; u <= n; u++) {
        for (int c = 1; c <= m; c++) {
            innerMax[c] = 0;
            totalMax[c] = grid[u][c];
        }

        for (int d = u + 1; d <= n; d++) {
            for (int c = 1; c <= m; c++) {
                totalMax[c] = max(totalMax[c], grid[d][c]);
                cornerMin[c] = min(grid[u][c], grid[d][c]);
            }

            vector<int> left;
            vector<int> rightMax;

            for (int c = 1; c <= m; c++) {
                while (not left.empty() and
                       cornerMin[left.back()] < totalMax[c]) {
                    int minCornerMin =
                        min(cornerMin[c], cornerMin[left.back()]);
                    if (minCornerMin > innerMax[c] and
                        minCornerMin > rightMax.back())
                        answer++;

                    int lastMax = max(rightMax.back(), totalMax[left.back()]);
                    left.pop_back();
                    rightMax.pop_back();
                    if (not rightMax.empty())
                        rightMax.back() = max(rightMax.back(), lastMax);
                }

                if (cornerMin[c] > innerMax[c] and not rightMax.empty() and
                    cornerMin[c] > rightMax.back())
                    answer++;

                if (not rightMax.empty())
                    rightMax.back() = max(rightMax.back(), totalMax[c]);

                if (cornerMin[c] < innerMax[c])
                    continue;

                left.push_back(c);
                rightMax.push_back(innerMax[c]);
            }

            for (int c = 1; c <= m; c++)
                innerMax[c] = max(innerMax[c], grid[d][c]);
        }
    }

    println("{}", answer);

    return 0;
}

백준 28229번: Ammunition Storage [C++]