[동적 계획법 1] [C++] 2565번. 전깃줄

www.acmicpc.net/problem/2565

2565번: 전깃줄

 

 

입력

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.

출력

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.

---

해결 방법

처음 이 문제를 접했을 때 브루트 포스로 접근을 했었다.

특정 전깃줄을 제거했을 때 겹치는 전깃줄의 개수를 셈하려고 했다.

하지만 이를 구현하는 도중에 뭔가 잘못됐다는 것을 알고 다시 생각해보았고 LIS의 응용문제라는 것을 알았다.

 

우선 주어진 입력 값을 출발지점의 오름차순으로 정렬해보자. 아래와 같은 결과가 나온다.

1 8

2 2

3 9

4 1

6 4

7 6

9 7

10 10

 

도착지점의 결과를 갖고 LIS를 구해보자.

8	2	9	1	4	6	7	10
1	1	2	2	2	3	4	5

 

LIS의 값인 5가 제거하지 않고 남길 수 있는 전깃줄의 최대 갯수이다.

따라서 '전체 전깃줄의 개수 - LIS' 가 정답이다.

 

이렇게 끝내면 설명이 부실하니 어떻게 이 문제가 LIS에 관련되어 있는지를 살펴보자.

 

이 문제의 핵심은 교차하지 않게 전깃줄을 배치하는 것이다.

출발 지점을 오름차순으로 정렬하였으니 도착지점도 오름차순으로 정렬되면 전깃줄이 교차하지 않는다고 볼 수 있다.

따라서 오름차순 형태의 최대 길이, 즉 LIS가 제거할 필요가 없는 교차하지 않는 전깃줄의 최대 갯수이므로

'전체 전깃줄의 개수 - LIS'가 정답이 된다.

 

최종 코드는