BOJ 17555 - Blurred Pictures 링크
(2024.04.16 기준 P5)

문제

$N \times N$개의 픽셀로 이루어진 그림이 있다. 그림의 $i$번째 줄은 $a_i$번째 픽셀부터 $b_i$번째 픽셀까지 흐리지 않은 픽셀이다. 나머지는 전부 흐린 픽셀이다.
두 흐리지 않은 픽셀 사이에는 흐리지 않은 픽셀만 존재할 수 있다.
흐리지 않은 픽셀로만 이루어진 최대 정사각형의 변의 길이 출력

알고리즘

단조성을 이용한 이분 탐색

풀이

흐리지 않은 픽셀 중 아무거나 하나 선택해보자. 이 픽셀로부터 아무 방향이나 쭉 훑어보자. 흐리지 않은 픽셀 여부는 $1$, $1$, $\dots$, $1$, $0$, $0$, $\dots$, $0$과 같은 단조성을 띈다. 두 흐리지 않은 픽셀 사이에는 흐리지 않은 픽셀만 존재할 수 있다.와 같은 조건이 있기 때문이다.
그럼 여기서 최대로 이어진 픽셀의 개수는 이분 탐색으로 찾을 수 있게 된다.

$i$번째 줄의 구간 $[a_i, b_i]$를 살펴보자. 이 줄만 봤을 때, 연속 픽셀의 최대 개수는 $b_i - a_i + 1$이다. 이는 직관적으로 알 수 있다. 근데 이 개수는 어느 픽셀에서부터 세기 시작해야 할까? 바로 $a_i$번째부터 오른쪽으로나 $b_i$번째로부터 왼쪽으로 세어야 한다.
여기서 알 수 있는 점은 구간의 끝점에서부터 탐색을 시작해야 최대 개수를 찾을 수 있다는 점이다.

이제 선에서 면으로 확장시켜보자.
$j$번째 줄의 구간 $[a_j,b_j]$이 $i$번째 줄의 구간 $[a_i,b_i]$을 포함한다고 생각해보자. 그러면 가로 길이 $b_i - a_i + 1$, 세로 길이 $|i - j| + 1$의 직사각형을 찾을 수 있게 된다.

위의 세 점을 합쳐보자.

• $i$번째 구간 $[a_i,b_i]$의 두 끝점을 각각 정사각형의 꼭짓점으로 잡자. 이때, $a_i$는 정사각형의 왼쪽 위나 아래 꼭짓점이 되며, $b_i$는 정사각형의 오른쪽 위나 아래 꼭짓점이 된다.
• 정사각형은 위로 향할 수 있고, 아래로 향할 수 있다.
• 위로 향하는 정사각형의 최소 길이는 $1$, 최대 길이는 $min(b_i - a_i + 1, i + 1)$이다. 아래로 향하는 정사각형의 최대 길이는 $1$, 최대 길이는 $min(b_i - a_i + 1, N - i)$이다.
• 각 방향마다 이분 탐색으로 가능한 최대 길이를 찾는다. 판별하고자 하는 길이가 $x$, $i$번째 줄과 현재 방향으로 $x$만큼의 길이를 이루는 줄의 인덱스를 $j$라고 가정하자. $j$번째 줄의 구간 $[a_j,b_j]$이 $i$번째 줄의 구간 $[a_i,b_i]$을 포함한다면 길이 $x$의 정사각형을 찾은 것이다.

코드

• C++

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

typedef pair<int, int> pii;

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

    int N; cin >> N;
    vector<pii> W;
    for (int i = 0, l, r; i < N; i++) cin >> l >> r, W.push_back({l, r});

    int ans = 1;
    for (int i = 0; i < N; i++){
        auto [l, r] = W[i];

        // (i, l)을 왼쪽 밑 꼭짓점으로 사용하는 정사각형 중 최대 정사각형을 찾는다.
        int st = 1, en = min(r - l + 1, i + 1);
        while (st < en){
            int mid = (st + en + 1) >> 1;
    
            // i-mid+1번째 구간이 [l, l+mid-1] 구간을 포함한다면
            // 길이 mid의 정사각형을 찾은 것이다.
            auto [l_, r_] = W[i - mid + 1];
            if (l_ <= l && l + mid - 1 <= r_) st = mid;
            else en = mid - 1;
        }
        ans = max(ans, st);
    
        // (i, l)을 왼쪽 위 꼭짓점으로 사용하는 정사각형 중 최대 정사각형을 찾는다.
        st = 1; en = min(r - l + 1, N - i);
        while (st < en){
            int mid = (st + en + 1) >> 1;
    
            // i+mid-1번째 구간이 [l, l+mid-1] 구간을 포함한다면
            // 길이 mid의 정사각형을 찾은 것이다.
            auto [l_, r_] = W[i + mid - 1];
            if (l_ <= l && l + mid - 1 <= r_) st = mid;
            else en = mid - 1;
        }
        ans = max(ans, st);

        // (i, r)을 오른쪽 밑 꼭짓점으로 사용하는 정사각형 중 최대 정사각형을 찾는다.
        st = 1; en = min(r - l + 1, i + 1);
        while (st < en){
            int mid = (st + en + 1) >> 1;
    
            // i-mid+1번째 구간이 [l, l+mid-1] 구간을 포함한다면
            // 길이 mid의 정사각형을 찾은 것이다.
            auto [l_, r_] = W[i - mid + 1];
            if (l_ <= r - mid + 1 && r <= r_) st = mid;
            else en = mid - 1;
        }
        ans = max(ans, st);
    
        // (i, r)을 오른쪽 위 꼭짓점으로 사용하는 정사각형 중 최대 정사각형을 찾는다.
        st = 1; en = min(r - l + 1, N - i);
        while (st < en){
            int mid = (st + en + 1) >> 1;
    
            // i+mid-1번째 구간이 [l, l+mid-1] 구간을 포함한다면
            // 길이 mid의 정사각형을 찾은 것이다.
            auto [l_, r_] = W[i + mid - 1];
            if (l_ <= r - mid + 1 && r <= r_) st = mid;
            else en = mid - 1;
        }
        ans = max(ans, st);
    }

    cout << ans;
}

• Python

import sys; input = sys.stdin.readline

N = int(input())
W = [tuple(map(int, input().split())) for _ in range(N)]

ans = 1
for i in range(N):
    l, r = W[i]

    # (i, l)을 왼쪽 밑 꼭짓점으로 사용하는 정사각형 중 최대 정사각형을 찾는다.
    st = 1; en = min(r - l + 1, i + 1)
    while st < en:
        mid = (st + en + 1) >> 1

        # i-mid+1번째 구간이 [l, l+mid-1] 구간을 포함한다면
        # 길이 mid의 정사각형을 찾은 것이다.
        l_, r_ = W[i - mid + 1]
        if l_ <= l and l + mid - 1 <= r_:
            st = mid
        else:
            en = mid - 1
    ans = max(ans, st)

    # (i, l)을 왼쪽 위 꼭짓점으로 사용하는 정사각형 중 최대 정사각형을 찾는다.
    st = 1; en = min(r - l + 1, N - i)
    while st < en:
        mid = (st + en + 1) >> 1

        # i+mid-1번째 구간이 [l, l+mid-1] 구간을 포함한다면
        # 길이 mid의 정사각형을 찾은 것이다.
        l_, r_ = W[i + mid - 1]
        if l_ <= l and l + mid - 1 <= r_:
            st = mid
        else:
            en = mid - 1
    ans = max(ans, st)

    # (i, r)을 오른쪽 밑 꼭짓점으로 사용하는 정사각형 중 최대 정사각형을 찾는다.
    st = 1; en = min(r - l + 1, i + 1)
    while st < en:
        mid = (st + en + 1) >> 1

        # i-mid+1번째 구간이 [r-mid+1, r] 구간을 포함한다면
        # 길이 mid의 정사각형을 찾은 것이다.
        l_, r_ = W[i - mid + 1]
        if l_ <= r - mid + 1 and r <= r_:
            st = mid
        else:
            en = mid - 1
    ans = max(ans, st)

    # (i, r)을 오른쪽 위 꼭짓점으로 사용하는 정사각형 중 최대 정사각형을 찾는다.
    st = 1; en = min(r - l + 1, N - i)
    while st < en:
        mid = (st + en + 1) >> 1

        # i+mid-1번째 구간이 [r-mid+1, r] 구간을 포함한다면
        # 길이 mid의 정사각형을 찾은 것이다.
        l_, r_ = W[i + mid - 1]
        if l_ <= r - mid + 1 and r <= r_:
            st = mid
        else:
            en = mid - 1
    ans = max(ans, st)

print(ans)