구사과

데큐를 사용해서 Sliding window로 구간 최댓값 / 최솟값을 구하는 알고리즘이 잘 알려져 있다. 이 알고리즘에 inchworm을 적용하여서 문제를 해결할 수 있다. 처음에 [1, 1] 구간에서 시작하여. (최댓값) - (최솟값) $ \leq T$ 를 만족할 때까지 구간의 끝점을 늘린다. 더 이상 늘릴 수 없으면, 시작점을 늘리면서 계속한다. 이러한 식으로 구간의 길이를 최대화하면서 데큐를 관리해 주면 최대 구간의 길이를 알 수 있다.

이러한 류의 문제는 그래프 이론으로 해석하면 편한 경우가 많은데, 구간 그래프(Interval Graph) 에서 두 점 쌍이 주어졌을 때, 두 점간의 최단 경로를 계산하는 문제로 해석할 수 있다. 구간 그래프는 각 구간을 정점으로 하고, 두 구간이 겹칠 때 대응되는 정점들에 무향 간선을 이어주는 식으로 구성하는 그래프이다.

일반적으로 이러한 류의 최단 경로는 너비 우선 탐색이나 Floyd-Warshall으로 해결하지만, 이 문제에서는 입력이 굉장히 크기 때문에 $O(N^3)$ 같은 건 택도 없고, 쿼리당 $O(lgN)$ 에 가까운, 매우 빠른 시간에 해결해야 한다.

먼저, 두 구간 간의 최단경로를 빠르게 찾는 간단한 그리디 알고리즘을 생각해 보자. 만약에 두 구간이 겹친다면, 최단 경로는 자명히 1이다. 그렇지 않은 경우에는, 일반성을 잃지 않고 첫번째 구간의 끝점 < 두번째 구간의 시작점이라고 생각하자. 첫번째 구간과 겹치는 구간 중, 끝점이 가장 큰 구간을 찾아서 이동한다. 이렇게 가능한 구간들 중 끝점을 최대화하는 구간으로 이동하면, 언젠가 두번째 구간과 겹치는 구간을 찾게 될 것이고, 이 구간에서 두번째 구간으로 이동하면 된다. 이 그리디 전략이 최선인 것을 증명하는 것은 간단하다. 끝점을 최대화하는 구간을 고르지 않음으로써 최단 경로를 줄일 수 없기 때문이다.

이 방법을 사용하면, 각 쿼리를 $O(N)$ 에 해결할 수 있다. 처음에 구간을 끝점 순으로 정렬해 놓으면, 현재 구간에서 갈 수 있는 구간 중 끝점이 가장 큰 구간을 inchworm 비슷하게 찾을 수 있다. 이 과정을 $O(NlgN)$에 해 놓으면, $F[i] = $ ($i$번 구간에서 갈 수 있는 끝점이 가장 큰 구간의 번호) 를 다 계산할 수 있다. 질의가 들어왔을 때, 두 구간이 겹치지 않는다면, 첫번째 구간 $s$에 $F[s], F[F[s]], F[F[F[s]]], \cdots$ 를 반복적으로 적용시키고, 두번째 구간과 겹칠 때까지, 혹은 진전이 없을 때까지 ($F[s] == s$) 계속한다. 만약 진전이 없다면 경로가 없는 것이고, 구간이 겹쳤다면 $s = F[s]$ 를 몇번 적용시켰는지 세어주면 된다.

이를 $O(lgN)$에 최적화하는 것은 sparse table로 잘 알려진 동적 계획법을 쓰면 된다. $DP[i][j] = $ (j번 구간에 $F[*]$ 를 $2^i$번 적용시킨 결과) 라는 테이블을 생각해 보자. $DP[0][*]$ 는 $F[*]$과 동일하고, $DP[i-1][*]$를 알면 $DP[i][*]$를 알 수 있으며, 굳이 $N$번 이상 연산을 적용 시킬 필요가 없으니 $i \leq lg(N)$ 이다. 고로 $O(NlgN)$에 테이블을 만들 수 있다. 이제 쿼리가 들어오면, $2^17$번 적용시키면 구간이 겹치는지, $2^16$번 적용시키면 구간이 겹치는지.. 를 물어보는 식으로 이진 탐색을 할 수 있다. 이를 통해 $O(lgN)$ 에 문제를 해결할 수 있다. 이러한 류의 동적 계획법 테크닉은 Sparse table로 검색할 경우 많은 정보를 얻을 수 있을 것이다.

바로 떠오를 수 있는 DP 접근은, 현재 격자의 어떠한 부분 직사각형이 남아있는지를 가지고 DP를 하는 것이다. 정확히는, $DP[sx][ex][sy][ey] = $ ($[sx, ex] \times [sy, ey]$ 직사각형을 없애 버리는 데 필요한 최소 제거 횟수라고 정의하자. 경계선을 이루는 가로 / 세로줄을 제거할 수 있는지는, 부분합을 전처리하면 $O(1)$ 시간에 쉽게 알 수 있다. 고로 4개의 가로 / 세로 선에 대해서, 제거가 가능하다면 제거한 이후의 부분 직사각형 DP값을 보는 식으로 문제를 해결할 수 있다. 이 방법은 $O(N^2M^2)$의 시간 복잡도를 가져서, 문제를 해결하기에는 많이 부족하니, 다른 접근법을 생각해 보자.

먼저, 최소 제거 횟수라는 것의 의미를 조금 더 살펴보자. 여러 과정을 거쳐서 직사각형의 가로 / 세로줄을 제거하다 보면, 결국 마지막에 제거하게 될 직사각형은 $1 \times k$ 혹은 $k \times 1$ 모양일 것이다. 이 모양에 도달하는 동안 가로 세로 크기는 정확히 1씩 감소했고, 고로 $(N - k) + (M - 1)$번의 연산을 수행했음을 알 수 있다. 여기서 알 수 있는 것은, 마지막에 만드는 직사각형을 최대한 길쭉하게 만드는 것이, 답을 최소화하는 것과 동일하다는 것이다.

가로로 길쭉한 사각형, 즉 $1 \times k$ 사각형을 만든다고 하자. (구현 시에는 $0 \times k$ 로 생각하는 게 훨씬 편하다.) 가로를 최대한 길게 하려고 하니, 가로선을 굉장히 공격적으로 깎는 것이 전략이 될 것이다. 첫 상태에서 잘라서 없앨 수 있는 가로선을 최대한 없애고, 만약 교착 상태에 놓여 있다면, 왼쪽 세로선과 오른쪽 세로선을 둘 다 깎아본 후, 깎는 게 가능하다면 비슷한 방식으로 계속 recursive하게 진행한다.

이런 식으로 단순하게 백트래킹을 하면 시간 안에 돌지 않을 것이지만, 가로선은 그리디하게 처리하고 있으니, 현재 살아있는 세로선이 어떤 것인지만 중요하지 않냐는 생각이 든다. 즉, $[sy, ey]$ 구간을 이미 고려한 recursion이 있다면, 굳이 이 구간을 다시 처리할 필요가 있을까..? 그런데, $[sy, ey]$ 구간을 들어가는 recursion 중, 만약 가로선 구간 ($[sx, ex]$) 이 다른 것이 여러개 들어가면 틀린 풀이가 될 수도 있지 않을까?

조금 더 생각해 보면, $[sy, ey]$ 구간을 들어가는 recursion은 모두 같은 가로선 구간을 가진다. 만약에, 해당 구간의 가로선 중 합이 $k$ 초과인 것이 있다면, 이 가로선들이 구간의 경계를 결정할 것이고, 그러한 것이 없다면, 여기서 가로선 구간을 모두 지워버릴 수 있기 때문이다. 고로 $[sy, ey]$ 구간을 들어가는 recursion은 모두 같은 형태를 띌 것이며, 한번 방문한 상태는 다시 방문할 필요가 없다. 이를 DFS / BFS로 구현하면 만점이 나온다.

시간 복잡도가 $O(NM^2)$라고 생각할 수도 있겠지만, 잘 생각해보면 $O(NM)$이다. 증명은 독자들에게 남긴다. 간단하면서도 재밌다.

마지막에 만드는 직사각형을 길쭉하게 만든다는 아이디어까지는 위 풀이랑 동일하다. 가로로 길쭉한 사각형을 만들 때, 그 사각형의 양 끝 선을 지정해 줌으로써 정확히 무엇인지 지정해 줄 수 있다. 즉, 처음 직사각형에서 어떤 부분 직사각형을 잘라서 만들고 싶은지를 고정할 수 있다. 그렇다면, 단순 그리디로 자를 수 있을 때 계속 가로 / 세로선을 잘라나가면 이 부분직사각형을 정말 만들 수 있는지를 $O(N+M)$에 판별할 수 있다. 부분직사각형의 경우의 수가 $O(M^2)$ 이니 $O((N+M)M^2)$ 정도의 풀이를 찾을 수 있다.

이를 최적화할 수 있는 여지가 있을까..? 물론 있다. Pilots 문제와 똑같이 inchworm를 하면서, 시작점과 끝점을 동시에 움직이면 된다! 현재 구간이 안 되면 끝점을 늘리고, 되면 시작점을 늘려가면서 구간의 길이를 최대화하면 판별을 $O(M)$번만 시키면 된다. 고로 $O(NM)$에 문제를 해결할 수 있다.