17972 Network Vulnerability

$N$개의 구간이 주어집니다. 어떤 겹치는 두 구간 사이에 간선을 이어서 만든 그래프를 $G$라 합시다.

$k = 0, 2 .. N-1$에 대해, $G$에서 $k$개의 정점을 지웠을 때 남는 컴포넌트의 수의 최댓값을 구하는 문제입니다.

 

$O(N^3)$ Solution

일단 좌표압축을 통해 모든 좌표를 $[1, 2N]$으로 바꿔줍시다.

$DP[i][j]$를 $[1, i]$에 포함되는 구간으로만 이루어진 $j$개의 컴포넌트가 있을 때, $[1, i]$ 안에 남길 수 있는 구간 개수의 최댓값이라 정의합니다. 또, $S[i][j]$를 $i$ 에 왼쪽 끝점이 있고 오른쪽 끝점이 $j$이하인 구간의 개수라 합시다.

 

$x = k$에서 슥 자른다고 생각하면, 다음과 같은 전이를 생각해 볼 수 있습니다

$ DP[i][j] = max(DP[i][j], DP[k-1][j-1] + S[k][i])$  단 $(S[k][i] \geq 1)$

또 컴포넌트를 늘리지 않는다 생각하면

$DP[i][j] = max(DP[i][j], DP[i-1][j])$

 

$DP[i][j]$값은 $O(N^3)$에 쉽게 구할 수 있습니다.

실제 답을 구하는 과정은 $DP[2N][i] = x$라 하면, $N-x$개 이상 $N-i$이하의 정점을 지워서 $i$개의 컴포넌트를 만들 수 있다는 뜻과 동치이므로 $k\in [N-x, N-i]$인 $k$에 대해 $ans[k] = max(ans[k], i)$를 해주면 됩니다.

 

$O(N^2logN)$ Solution

 

$DP[i][j]$를 계산할 때, $i$를 하나씩 늘려가며 갱신해봅시다. 전이 가능한 모든 쌍을 둘러보면 $O(N)$이므로 위와 같이 세제곱이 됩니다. 하지만 세그먼트 트리를 이용하면 $O(logN)$에 전이가 가능합니다.

 

세그먼트 트리의 $i$번째 값을 DP[i][j-1]로 갱신해줍시다. 문제는 여기서 $S[i][j]$도 더해줘야 한다는 것인데, 이는 $i$에 증가에 따라 추가로 범위에 포함되는 구간마다 1을 더해줌으로써 해결할 수 있습니다.

즉, 새로운 구간이 들어올 때마다, 적당한 $[l, r]$에 $1$을 더해줌으로써 $S[i][j]$를 더한 것과 같은 기능을 구현할 수 있습니다.

구간 $add$ 연산과 구간 $min$연산 2개를 지원하는 레이지 세그먼트 트리를 짜면 됩니다.

총 시간복잡도는 $O(N^2logN)$입니다.