💔전깃줄

 

1. 문제 설명

2565번: 전깃줄

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

 

www.acmicpc.net

두 개의 전봇대가 존재한다. 두 전봇대 사이엔 여러 전깃줄이 존재한다. 전봇대의 높이는 1~10으로 표현되는데, 전깃줄은 다음 그림과 같이 겹칠 수 있다.

최소한의 전깃줄을 제거해서 모든 전깃줄이 서로 교차하지 않도록 만들어라.

2. 푸는 원리

해당 문제를 LIS로 생각만 할 수 있다면 쉽게 풀리는 문제다. 하지만 그렇게 생각하기가 꽤나 어렵다. 따라서 필자는 먼저 전깃줄 문제를 어떻게 LIS 문제로 볼 수 있는지부터 설명하고자 한다. 위 사진의 A 전봇대를 기준으로 생각해보자. A 전봇대는 제일 높은 높이를 1, 제일 낮은 높이를 10이라 두어 정렬되어 있다. 그리고 각 높이 칸마다 혹 전깃줄을 가지고 있으면 반대편 전봇대 B의 특정 높이 칸과 연결되어 있음을 알 수 있다. 예를 들어 전깃줄의 기호를 L(A전봇대에서의 위치, B 전봇대에서의 위치)라고 한다면 첫번째 전깃줄 L1 = L(1,8)이다. (왼쪽에선 1번 칸, 오른쪽에선 8번칸에 위치) 그렇다면, 전깃줄이 꼬이지 않으려면 어떻게 해야 하는가? 전봇대 A와 B의 각 위치를 배열로 나타냈을 때, A[i] < A[j] 이면 B[i] < B[j] 이면 된다. 예를 들어 아까 L1(1,8) 이었다. 그렇다면 A의 2번째 칸에서 시작하는 전깃줄이 L1과 교차되지 않으려면 어떻게 해야하는가? L2(2,9) 이거나 L2(2,10)이면 된다. 절대 L2(2,1) ~ L2(2,8)의 값 중 하나이면 안된다. 자 이제 LIS가 조금 보이는가? 그렇다, 최소한의 전깃줄을 제거해서 교차되지 않는 전깃줄의 배열을 만든다는 소리는 현재 주어진 전깃줄을 교차되지 않게 가장 많이 살리는 것과 같은 말이다. 교차되지 않게 전깃줄을 놓으려면 각 전깃줄이 A[i] < A[j] 이면 B[i] < B[j] 이면 된다.을 만족하는 부분 증가 수열이면 된다는 소리이다! 이때 A의 값를 인덱스, B의 값을 해당 인덱스의 값으로 보면 된다. 우리가 구하려는 제거하는 전선의 최소 개수는 [전체 전깃줄의 개수] - LIS 가 된다. 그 다음은 전형적인 LIS 풀이를 사용해서 풀면 된다.

3. 코드 분석

Copy