BOJ 15977 - 조화로운 행렬

매우 유명한 문제이다. 당연히 좋은 풀이글도 많고 다양한 풀이가 존재하지만, 좋은 문제라 정리하는 것이 의미가 있을 것 같아 따로 정리해본다. 더불어, LIS를 \(O(NlogN)\)으로 해결하는 방법에 대한 튜토리얼 글들을 보면 원리를 제대로 설명하지 않은 글들이 많아 이를 정확히 설명하고, 이 문제의 해법까지 이어가는 것이 이 글의 목표이다.

 

문제 요약

 

서로 다른 양의 정수로 이루어진 \(2 \times N\) 또는 \(3 \times N\) 행렬이 주어질 때, 각 행에서의 등수가 같도록 뽑을 수 있는 열의 최대 개수를 구하시오.

 

풀이

가장 윗 행을 기준으로 정렬하고 나면 \(M = 2\)인 경우 LIS (Longest Increasing Sequence), \(M = 3\)인 경우 Pair LIS ( \(P_1 = (X_1,Y_1)\), \(P_2 = (X_2, Y_2)\) 에 대해 \(P_1 < P_2 = X_1 < X_2, Y_1 < Y_2\)로 정의한다.) 의 길이를 구하는 문제임이 자명해진다. 만약 \(M = 2\)인 경우 \(P_i = (X_i, X_i)\)로 정의하면 되니, 일반성을 잃지 않고 \(M = 3\)이라고 생각할 수 있다. 

 

1차원 LIS의 경우에는 \(O(NlogN)\)으로 해결하는 풀이가 여럿 알려져 있으며, 그 중에도 가장 널리 알려진 방법이 이진탐색을 이용하는 것이다. 하지만, 이 방법에서 정의하는 배열이 의미하는 바가 정확히 무엇인지, 이진탐색을 왜 이용하는지 알지 못한다면 2차원으로의 해법으로 발전시키기 힘들다. 

 

LIS의 DP식을 먼저 생각해보자. \(DP[i] = \max_{j<i, A_j < A_i} (DP[j]) + 1\) 이다. \(O(N^2)\) 해법은 모든 \(j\)에 대해 이를 확인하는 것이다. 이를 \(O(NlogN)\) 풀이로 발전시키기 위해서는 두 가지 관찰이 필요하다.

 

1. 같은 DP값을 가지는 인덱스들 중에는 \(a_i\) 의 최솟값만 저장해도 된다. 이 배열을 \(B\)라 하자.

2. 그리고, 이는 DP값에 따라 증가한다.

 

1은 자명하고, 2는 \(B\)를 업데이트 하는 방식이 \(B[j] < A[i]\)를 만족하는 가장 큰 \(j\)를 찾아 \(DP[i] = j+1\)로 정의하고, \(B[j+1]\)을 \(A[i]\)로 갱신해주는 것이기 때문에 항상 성립한다. 처음의 \(B\)는 비어있으므로 정렬된 상태고, 저 연산을 적용할 시 정렬된 상태가 유지되기 때문이다.

 

이 풀이를 2차원에 적용시키기 위해 위 관찰들을 일반화해보자.

 

1. 같은 DP값을 가지는 인덱스들 중, \(P_i < P_j\)인 경우가 있다면 \(P_i\)인 경우만 저장해도 된다. \(P_i\) 뒤에 올 수 있는 값의 후보가 \(P_j\) 뒤에 올 수 있는 값의 후보를 포함하기 때문이다.

 

즉, 2차원 기준으로 같은 DP값을 가지는 값들을 모았을 때 불필요한 점을 제거하고 난 후 x좌표 오름차순으로 정렬하면 y좌표는 감소하게 된다. \(X_i < X_j, Y_i < Y_j\)인 경우가 없기 때문이다. 이러한 점들을 set으로 관리해주자.

 

2. 그리고, 이는 DP값에 따라 증가한다.

 

이를 조금 더 자세히 해석하면, 1차원 기준으로 어떤 \(j_0\)가 존재해 \(B[j_0] < A[i]\)를 만족하다면 \(j \leq j_0\)인 \(j\) 역시 이를 만족한다는 것이다. 이를 2차원에 적용하면, 어떤 \(j_0\)가 존재해 \(set[j_0]\)에 \(P_k < P_i\)인 점이 존재한다면 \(j \leq j_0\)인 \(set[j]\)에도 이러한 점이 존재한다는 것이다. 이는 LIS의 정의를 생각해보면 자명하다. \(DP[i]\)는 \(j_0 + 1\)의 값을 가지게 된다.

 

이제 남은 부분은 두 가지이다.

 

1. 어떤 \(j\)에 대해 \(set[j]\)에 \(P_k < P_i\)인 점이 존재하는지 판별

 

이를 수행할 수 있어야만 \(j_0\)를 이분탐색으로 찾는 것이 가능해진다. 여기에는 각 set이 x좌표에 대해 오름차순, y좌표에 대해 내림차순이라는 성질을 이용한다. \(X_k < X_i\)인 최대의 \(k = k_0\)에 대해, \(k \leq k_0\)인 점들은 모두 \(X_k < X_i\)를 만족하며, 이 점들 중 \(k_0\)가 가장 작은 y좌표를 갖는다. 따라서, \(k_0\)의 y좌표가 \(Y_i\)보다 작은지만 판별해주면 된다.

 

2. 각 set을 정렬된 상태로 관리

 

이는 새 점을 set에 삽입할 때 x좌표가 새 점보다 큰 점들을 순서대로 보며 y좌표도 새 점보다 크다면 삭제하는 것을 반복해주면 된다. 각 점은 최대 1번 삽입되고 삭제되므로 amortized \(O(N)\)번 수행한다.

 

이를 고려하며 코딩해주면 AC를 받을 수 있다. LIS에 대한 완벽한 이해를 요구하는 좋은 문제라고 생각한다.

 

설명에 이상한 부분이 있다면 말씀해주시기 바랍니다.