글 읽기 - Interval Graph 및 Vertex Cover 관련

안녕하세요, 해당 문제를 풀어보려 하다가 막막하여 글을 남깁니다.

저는 문제를 각 구간을 정점으로 하는 그래프에서 Vertex Cover 의 개수를 구하는 문제로 해석했습니다.

하지만 다음 2가지 작업에서 정체되어버렸습니다.

- 주어진 구간을 그래프로 빠르게 변형하는 방법

- Vertex Cover 의 개수를 구하는 방법

검색을 해보니 Vertex Cover 의 Complement 인 Independent Set 을 이용할 수 있는 것 같은데 영 감이 안 잡힙니다..

버텍스 커버를 구하는 알고리즘은 NP 문제로 절대로! 프로그래밍 문제로 제출할리가 없습니다.

낸다손 쳐도 N이 32 이하인 웬만하면 휴리스틱으로 풀리는 문제로 내죠.

힌트를 준다면, 감시로봇이 검사하는 구간을 X, Y 라고 했을때 Y축으로 정렬해보세요. 이후에

어떤 감시로봇을 사용 하지 않는다면 X구간 이전에 있던 경우의 수만 고려해야 되고

만약 이 감시로봇을 사용한다면 "지금까지" 구한 가능한 모든 경우의수가 가능합니다.

답변이 많이 늦었네요. 힌트 감사합니다. 고민해보고 시도해봐야겠네요.

댓글을 작성하려면 로그인해야 합니다.

Baekjoon Online Judge