백준 4198 - 열차정열

사실 열차정렬입니다.

https://www.acmicpc.net/problem/4198

4198번: 열차정렬

이 문제는 아래 문제를 풀고나서 접한다면 뭔가 느낌 오는 게 있을 것이다. 아니면 적어도 LIS 문제라도 풀고 접하는 편을 추천한다.

 

가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054

 

내가 처음에 긴가민가했던 이유는, 예시 입력 데이터가 너무 단순했기 때문이라고 핑계를 대고 싶다.

다음의 입력 데이터를 보자. (차량 수 N은 생략)

 

5 3 1 7 8

 

짱구를 약간만 굴려보면 이런 식의 열차를 만들 수 있다.

8 7 5 3 1

 

아래의 데이터들에서도 동일한 열차를 만들 수 있을 것이다.

5 3 7 8 1  /  5 7 8 3 1

 

그러나 이런 데이터에서는 위 열차를 만들 수 없다.

5 3 1 8 7  /  5 1 3 7 8

 

이 데이터들의 차이점은 무엇일까?

유효한 위쪽 데이터들은 일부 원소의 순서가 바뀌더라도, 첫 원소 5에서 시작하는 IS(증가 부분수열)와 DS(감소 부분수열)가 유지된다.

 

5 3 7 8 1  /  5 7 8 3 1

 

하지만 아래 데이터들은 원소의 위치가 바뀌어 IS와 DS 길이가 감소한다.

5 3 1 8 7  /  5 1 3 7 8

 

결론적으로, 입력 데이터로 만들 수 있는 열차의 길이는 각 원소에서 시작하는 L(longest)IS와 LDS의 길이 합들 중 최댓값이다! 물론 합에서 1을 빼야한다. 이제 dp 알고리즘을 이용해 간단하게 문제를 풀 수 있을 것이다.