[ICPC 본선 대비 뇌셋] Day 21

ICPC 본선 대비 뇌셋 포스팅 대망의 마지막 날이다. 작년에 못풀었던 문제들중 한문제인 2019년 ICPC Korea regional E번을 생각해봤다. 자료구조까지는 생각하지 않았지만, $O(N^2 lg(N))$에 풀리게 생겼다.

백준 17972번 Network Vulnerability www.acmicpc.net/problem/17972

17972번: Network Vulnerability

좌표압축으로 모든 점이 1~2N안에 있다고 하자. 우리는 총 j개의 connected component(CC)가 있을 때 남아있을 수 있는 구간(노드) 개수의 최대값을 구할 것이다. 이를 구하면 정답을 쉽게 구할 수 있다.

N = 2000이므로 2차원 DP를 세우면 될 것 같다는 생각을 할 수 있다.

따라서 dp[i][j]를 1~i번 안에 속하는 구간들로 이루어진 j개의 CC 개수의 최댓값이라고 하자. 또, i 에서 시작하고 j로  포함되는 구간의 개수를 S[i][j] 라고하자.

한편, j개의 CC가 있을 때, 제일 오른쪽 CC를 자르는 왼쪽 경계를 생각해볼 수 있고, 이를 통해서 dp식을 다음과 같이 쓰자.

for 경계 k : 1 to N, for 오른쪽 끝 r : k to N (단, k에서 시작하는 component와 연결되어 있어야 함.)

$dp[r][m+1] = max(dp[r][m+1], dp[k-1][m] + S[k+1][r])$

$O(N^3)$이다.

여기서 세그트리를 쓰면 $O(N^2lg N)$에 된다고 하지만, 그냥 $O(N^3)$코드를 적절히 최적화 잘 해주면 3초 안에는 돌아갈 것 같다.