[백준 2550번] 전구 ( java)

 

백준 전깃줄 문제와 유사하다. 

이진탐색을 사용한 증가하는최장부분수열(LIS)을 구하는 문제이다.

다만, 수열의 길이만 구하는 것이 아니라 수열 자체도 구해야 하므로 역추적하는 배열이 별도로 필요하다.

역추적을 통한 증가하는최장부분수열의 수열 구하는 방법은 아래 포스팅에 나와있다.

 

LIS(Lowest Increasing Subsequence) - 수열 구하기

 

이 문제는 전선이 만나지 않도록 하면서 전구가 가장 많이 켜지도록 하는 경우를 구하는 문제이다.

두 전선이 꼬이지 않기 위해서는 스위치 번호도 증가하는 수열이 되면서, 전구의 번호도 증가하는 수열이 

되면 된다.

 

아래 그림을 보면,

왼쪽 그림의 경우 스위치에서의 순서도 4->1->3 이고, 전구에서의 순서도 4->1->3 으로, 1,3,4 간의 순서가 스위치와 전구에서 뒤바뀌지 않고 유지된다.

오른쪽 그림도 마찬가지로, 스위치에서의 순서는 4->5->3 이고, 전구에서의 순서도 4->5->3 이므로,

3,4,5 간의 순서가 스위치와 전구에서 뒤바뀌지 않고 유지된다.

 

 

이럴 경우에만 전선이 꼬이지 않고 모든 전구에 불이 들어올 수 있다.

이 문제를 최장증가부분수열로 해결하기 위해 각 번호에 인덱스를 부여하였다.

(아래 그림에서 빨간색 숫자가 인덱스)

 

 

전구에서의 인덱스 1, 3, 2, 4, 0 에서 최장증가부분수열을 찾으면 된다.

(자세한 LIS 알고리즘은 위의 포스팅 링크를 참고)

스위치에서의 인덱스는 어차피 0, 1, 2, 3, 4로 오름차순으로 정렬되어 있으므로 신경쓸 필요가 없다.

최장증가하는부분수열은 1, 3, 4 혹은 1, 2, 4가 될 것이고, 해당 인덱스에 해당하는 숫자들인

4, 5, 3 혹은 4, 1, 3이 답이 된다.