[BOJ] 2568 전깃줄 - 2 (C/C++)

2568번: 전깃줄 - 2

문제

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

예를 들어, <그림 1>과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 

그림 1

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 최소 개수의 전깃줄을 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다. 둘째 줄부터 한 줄에 하나씩 없애야 하는 전깃줄의 A전봇대에 연결되는 위치의 번호를 오름차순으로 출력한다. 만약 답이 두 가지 이상이라면 그 중 하나를 출력한다.

---

 

2565번: 전깃줄

6개월 전쯤에 DP로 비슷한 문제를 풀었었다. 그때는 없애야하는 전깃줄의 최소 개수만 구하는 문제였지만 이번에는 실제로 삭제한 전깃줄도 알아내야 했다.

 

일단 그래서 이 문제도 DP로 풀어야할 줄 알았는데 풀다 보니 뭔가 잘 들어맞지 않아서 가장 긴 부분 증가수열 알고리즘을 사용했다. 이전에도 이 알고리즘을 사용해서 다른 문제를 풀었는데, 그때는 단순히 lower_bound 함수를 사용해서 반복자를 받아와서 값을 수정해줬다. 이번에는 없앤 전깃줄을 알아내야 해서 벡터를 하나 더 사용했다.

 

처음엔 입력을 받기 위해서 map을 사용하고 싶었는데 인덱스를 알아내야 해서 쓰지 못 했다. 방법이 있을지도 모르겠지만 map을 몇 번 사용해보지 않아서 잘 모른다... 

 

LIS를 구하기 전에 A 값을 기준으로 벡터를 정렬한다. 그 다음에 순서대로 보면서 LIS에는 B의 값을 집어넣는다. 선을 자르지 않아도 되는 경우와 선을 자르는 경우가 나뉘어 있는데 두 경우 모두 idx 벡터에 값을 집어넣는다. 나중에 잘린 선이 어떤 건지 확인하려고 사용한다. 잘린 선의 개수는 총개수에서 LIS의 크기를 빼면 된다.

 

잘린 선을 확인하기 위해서는 LIS의 인덱스와 idx에 들어있는 값을 비교한다. 만약 LIS의 인덱스와 idx의 값이 같은 경우엔 그 선은 살아있는 선이므로 내비두고 다른 경우엔 정답 배열에 추가한다. 그 배열을 역순으로 출력하면 정답을 얻을 수 있다.

 

 

후기)

이제 방학도 다 끝나가는데 1월, 2월에 모두 쉬지 않고 블로그 포스팅한게 뿌듯하다. 매번 깃허브에도 올렸어야 했는데 깃허브에는 올리는걸 하루 빼먹어서 하루가 빈다. 그게 좀 아쉽다.