[백준] 동적 계획법 - 11054: 가장 긴 바이토닉 부분 수열 (Java)

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

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가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

이 문제를 풀기 위해서는 가장 긴 증가하는 부분 수열(풀이)을 먼저 풀어보기 바란다.

가장 긴 증가하는 부분수열은 증가하는 부분 수열을 찾는 것이라면, 바이토닉 부분수열은 증가하다 감소하는 수열 중 가장 긴 값을 찾는 것이다. (증가만, 감소만, 증가하다 감소)

문제의 예시로 풀이를 해보겠다.

증가만 하는 수열 // ->

1	5	2	1	4	3	4	5	2	1
1	2	2	1	3	3	4	5	2	1

dp[0] ={1}

dp[1] ={1, 5}

dp[2] ={1, 2}

dp[3] ={1}

dp[4] ={1, 2, 4}

dp[5] ={1, 2, 3}

dp[6] ={1, 2, 3, 4}

dp[7] ={1, 2, 3, 4, 5}

dp[8] ={1, 2}

dp[9] ={1}

감소만 하는 수열(오른쪽에서 증가하는 수열) // <-

1	5	2	1	4	3	4	5	2	1
1	5	2	1	4	3	3	3	2	1

dp[0] ={1}

dp[1] ={1, 2, 3, 4, 5}

dp[2] ={1, 2}

dp[3] ={1}

dp[4] ={1, 2, 3, 4}

dp[5] ={1, 2, 3}

dp[6] ={1, 2, 4}

dp[7] ={1, 2, 5}

dp[8] ={1, 2}

dp[9] ={1}

가장 긴 바이토닉 수열은 어떻게 구하는가? 두 수열의 결과를 더하면 된다.

입력	1	5	2	1	4	3	4	5	2	1
증가	1	2	2	1	3	3	4	5	2	1
감소	1	5	2	1	4	3	3	3	2	1
합	2	7	4	3	7	6	7	8	4	2

우리가 원하는 결과는 7이다. 그런데 왜 7인가? 가장 많은 수를 찾으면 되나? 아니다.

합에서는 해당 입력이 두 번씩 들어간다. 그래서 결과에서 1 씩 빼주어야 진짜 결과이다.

그래서 최댓값인 8에서 1을 빼준 7이 진짜 답이다.