취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5479번 문제인 Pyramid이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/5479

각 $a$열 $b$행의 사각형 영역 내부에 있는 $c$열 $d$행의 영역 중 "영역의 테두리 칸을 포함하지 않고, 안에 적힌 수의 합이 가장 작은 영역"을 빠르게 찾을 수 있다면 문제를 어렵지 않게 해결할 수 있을 것이다.

각 칸을 한쪽 구석으로 하는 $c$열 $d$행의 사각형 영역에 적힌 수의 합을 나타내는 2차원 배열을 하나 만들자. 이 배열에서의 사각형 영역에서의 최솟값 쿼리를 처리할 수 있다면 문제 해결에 어려운 점이 없을 것이다.

업데이트가 없는 2차원 배열에서의 사각형 영역 최솟값 쿼리는 전처리 후 2D Sparse Table, 2D Segment Tree 등을 이용하여 빠르게 구할 수 있다. 글쓴이는 (BOJ에 존재하는 태그 기준으로) Deque Range Minimum Trick을 활용해 문제를 해결하였다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <deque>
using namespace std;

int R, C, RR, CC, RRR, CCC;
int A[1001][1001];
int B[1001][1001];
int psum[1001][1001];


int ans, ansrr, anscc, ansrrr, ansccc;
int ansmn = 0x3f3f3f3f;

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

    cin >> C >> R >> CC >> RR >> CCC >> RRR;
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            cin >> A[r][c];
            psum[r][c] = A[r][c] + psum[r - 1][c] + psum[r][c - 1] - psum[r - 1][c - 1];
        }
    }
    for (int r = RRR; r <= R; r++) {
        for (int c = CCC; c <= C; c++) {
            B[r][c] = psum[r][c] - psum[r - RRR][c] - psum[r][c - CCC] + psum[r - RRR][c - CCC];
        }
    }
    for (int r = RR; r <= R; r++) {
        deque<pair<int, int>> dq;
        for (int cc = CCC + 1; cc < CC; cc++) { // 지금 영역: r - RR + 1 ~ r행, c - CC + 1 ~ c열
            int tmp = 0x3f3f3f3f;
            for (int rr = r - RR + 1 + RRR; rr < r; rr++) {
                tmp = min(tmp, B[rr][cc]);
            }
            while (!dq.empty() && dq.back().first >= tmp) dq.pop_back();
            dq.push_back(make_pair(tmp, cc));
        }
        for (int c = CC; c <= C; c++) {
            while (!dq.empty() && dq.front().second < c - CC + 1 + CCC) dq.pop_front();
            int X = psum[r][c] - psum[r - RR][c] - psum[r][c - CC] + psum[r - RR][c - CC];
            int Y = dq.front().first;
            int val = X - Y;
            if (ans < val) ans = val, ansrr = r, anscc = c;

            
            int tmp = 0x3f3f3f3f;
            for (int rr = r - RR + 1 + RRR; rr < r; rr++) {
                tmp = min(tmp, B[rr][c]);
            }
            while (!dq.empty() && dq.back().first >= tmp) dq.pop_back();
            dq.push_back(make_pair(tmp, c));
        }
    }

    for (int rr = ansrr - RR + 1 + RRR; rr < ansrr; rr++) {
        for (int cc = anscc - CC + 1 + CCC; cc < anscc; cc++) {
            if (ansmn > B[rr][cc]) ansmn = B[rr][cc], ansrrr = rr, ansccc = cc;
        }
    }

    cout << anscc - CC + 1 << ' ' << ansrr - RR + 1 << '\n';
    cout << ansccc - CCC + 1 << ' ' << ansrrr - RRR + 1 << '\n';
}

BOJ Random Defense #23