백준 11054번 가장 긴 바이토닉 부분 수열

백준 11054번

가장 긴 바이토닉 부분 수열

이 문제는 유명한 문제인 LIS(Longest Increasing Subsequence)를 활용하여 해결할 수 있다.

예제 입력과 출력으로 주어진 것을 먼저 살펴보자.

1 5 2 1 4 3 4 5 2 1 이 주어졌다.
이 때, 두 번째 원소에서의 바이토닉 부분 수열의 길이를 살펴보면

1 5
5 4 3 2 1 의 두 부분으로 나누어서 볼 수 있다.

1 5 는 해당 인덱스에서의 LIS 이고
5 4 3 2 1은 해당 인덱스에서 역으로 생각할 수 있는 LIS이다.

즉,

가장 긴 바이토닉 부분 수열은 인덱스에서의 LIS와 역 LIS를 각각 구해서 붙인 수열이다.

소스 코드로 이를 살펴보자.

s_f 배열은 기존의 리스트를 통해 구한 각 인덱스에서의 LIS 길이
s_b 배열은 역 리스트에서 구한 각 인덱스의 LIS 길이이다.

이후 마지막 반복문에서 각각의 길이를 더해주는 것으로 바이토닉 수열의 길이를 구한다.

1을 빼준 이유는 해당 인덱스의 원소가 두 번 더해지기 때문이다.