Baekjoon | 가장 긴 바이토닉 부분 수열

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

---

 

문제 

바이토닉 수열: 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족하는 경우

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하기

문제 해결 방법

이 문제는 지난번에 LIS 문제를 푼 기억을 가지고 접근했다.

처음에는 LIS를 구하여 max 값을 가지는 인덱스를 기준으로, 마지막 인덱스부터 가장 긴 증가하는 수열을 구하였다. 

그러나 아래 풀이 중 ! 와 같이 위 풀이는 모든 경우를 해결 할 수 없다.

결국 각 인덱스 별로 LIS + LDS를 구하는 것이 핵심으로, 더한 값에서 중복된 인덱스 1(LIS 한번 + LDS 한번 = 2)을 감소시키면 답을 구할 수 있다.

제출 코드

Go to Github