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

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/11054)

풀이

가장 긴 증가하는 부분 수열, 가장 긴 감소하는 부분 수열을 풀고나서 푼 문제입니다. 앞에 두 문제를 안 푸신분들은 먼저 2개를 풀고나면 쉽게 풀리는 문제임을 알 수 있습니다. 어떠한 수를 기준으로 앞쪽은 오름차순이 되어야하고, 뒤쪽은 내림차순이 되어야 합니다. 저는 그래서 dp라는 배열대신 up, down 배열을 만들어서 가장 긴 증가, 감소하는 부분 수열을 각각 만들어 주었습니다. 증가하는 부분은 -> 앞에서부터 오른쪽으로 진행하며 계산하고 감소하는 부분은 뒤에서부터 <- 왼쪽으로 진행하며 계산했습니다. 이렇게 되면 증가하는 부분+감소하는 부분이 가장 큰 값이 원하는 정답입니다! 하지만 증가하는 부분, 감소하는 부분에는 둘 다 기준이 되는 수가 2번 포함되어 있는 것이기 떄문에 up[i]+down[i]-1 이 최종적으로 원하는 답이 됩니다.

코드

https://github.com/kswim/Algorithm/blob/master/DP/11054.cpp