초고속철도 (KOI 2007)

https://www.acmicpc.net/problem/2543

 

Interval Graph에서의 Vertex Cover의 개수라는 말로 이 문제를 한줄요약할 수 있다.

하지만 말하는 그대로 dp를 짜기에는 상황이 너무 복잡하다. dp가 애초에 되는지 잘 모르겠다.

 

여기서 Vertex Cover의 정의를 잠깐 훑고 가자면

"그래프의 모든 간선에 대해, 최소 1개의 정점이 집합 S에 속하도록 하는 정점의 부분집합 S" 이다.

 

때문에 S의 여집합 I는

"그래프의 모든 간선에 대해, 최대 1개의 정점이 집합 I에 속한다"

라는 성질을 만족한다. 즉 I는 그래프의 독립 집합이다.

 

즉 Vertex Cover의 여집합은 Independent Set이라는 것을 알고 있으면 이 문제를 풀 수 있다.

Interval Graph에서 Independent Set의 개수를 구하는 건 그렇게 어렵지 않기 때문이다.

 

그래도 구하는 방법을 굳이 설명하자면,

dp(i) -> i번 정점을 포함하는 Independent Set의 경우의 수 라는 식으로 점화식을 짜면

dp(i) = Sum (Ei < Sj) dp(j) 이다.

Ei < Sj를 만족하는 최소의 j를 Low(i) 라 정의하면, dp(i) = Sum(Low(i) <= j) dp(j) 이며,

답은 Sum(0 <= i < N) dp(i) 이다. Low(i)는 이진 탐색으로 각각 O(lgN)에 구할 수 있으며, dp(i)는 각각 O(N) 이므로 O(N^2) 풀이가 이것이다. 

 

이를 O(N) 으로 풀기 위해서는 부분 합을 사용하면 된다. Sum(i) = Sum(i <= j < n) dp(j) 라고 정의하면,

S(i) - S(i+1) = S(low(i)) 라는 식이 나오며, S(i) = S(i+1) + S(low(i)) 라는 깔끔한 식으로 변형할 수도 있다.

출력 시에는 S(0)을 출력하면 되고, 중간에 이진 탐색과 정렬이 필요하니 복잡도는 O(NlgN)이다.