[PS] 11054:가장 긴 바이토닉 부분 수열 C++

11054:가장 긴 바이토닉 부분 수열

문제

수열 S가 어떤 수 Sk를 기준으로 $S_1 < S_2 < ... S_{k-1} < S_k > S_{k+1} > ... S_{N-1} > S_N$을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제 입력

10
1 5 2 1 4 3 4 5 2 1

예제 출력

7

풀이

• 이전에 풀었던 11053 가장 긴 증가하는 부분 수열 에서의 DP 접근 풀이를 참고 하였다.
• 가장 긴 증가하는 부분 수열 문제에서의 DP 접근법은 다음과 같았다.
  - 주어진 수열을 $a_0, a_1, ..., a_N$ 이라 하자.
  - 길이가 $N$인 dp 배열 $dp_0, dp_1, ..., dp_N$ 라 하자.
  - 점화식 표현:
  - $dp_i = \begin{cases} 1 & i=0 \\ \max(1, \{dp_j | 0\le j \lt i, a_j \lt a_i \}) & \text{else} \\ \end{cases}$
  - 즉, $dp_i$ 는 "i번째 원소로 끝나는 가장 긴 증가하는 수열의 길이"이다.
• 가장 긴 감소하는 부분 수열 문제에서의 DP 접근법은 다음과 같았다.
  - 위 dp 점화식을 N-1번째부터 0번째까지로 역순으로 적용하면, $dp_i$ 는 "i번째 원소에서 시작하는 가장 긴 감소하는 수열의 길이"이다.
• 이를 두 문제를 활용해 풀어보면,
  - 아이디어는 "가장 긴 부분 증가하는 수열의 길이"
  와 "가장 긴 감소하는 부분 수열의 길이"를 더하는 것이다.
  - 우리의 dp 테이블 : i번째 원소까지의 가장 긴 증가하는 부분수열의 길이 + i번째나 이후 원소부터 시작하는 가장 긴 증가하는 부분수열의 길이

코드

#include <string>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
using namespace std;

/**
 * Longest Bi-tonic  subsequence
 *
 * - Longest Increasing Subsequence : dp of dp of longest subsequence ending at i-th elem.
 * - Longest Decreasing Subsequence : dp of length of longest subsequence ending at j-th elem.
 * -> Longest Bitonic Subsequence :
 *  - iterate on inc/dec dp elem -> add possible largest inc/dec subsequence
 *   - find max on new dp
 *
 */

int main()
{
    int N;
    cin >> N;
    vector<int> seq(N);
    vector<vector<int>> dp(3, vector<int>(N, 1));

    for (int i = 0; i < N; i++)
        cin >> seq[i];

    // Get inc subsequence dp table
    for (int i = 0; i < N; i++)
        for (int j = 0; j < i; j++)
            if (seq[i] > seq[j])
                dp[0][i] = max(dp[0][i], dp[0][j] + 1);

    // Get dec subsequence dp table
    for (int i = N - 1; i > -1; i--)
        for (int j = N - 1; i < j; j--)
            if (seq[i] > seq[j])
                dp[1][i] = max(dp[1][i], dp[1][j] + 1);

    // Get bitonic subsequence dp table
    int res = 0;
    for (int i = 0; i < N; i++)
    {
        if (i == 0 || i == N - 1)
        {
            dp[2][i] = max(dp[0][i], dp[1][i]);
            res = max(res, dp[2][i]);
        }
        else
            for (int j = i; j < N; j++)
            {
                if (seq[i] == seq[j])
                    dp[2][i] = max(dp[2][i], dp[0][i] + dp[1][j] - 1);
                else if (seq[i] > seq[j])
                    dp[2][i] = max(dp[2][i], dp[0][i] + dp[1][j]);
                res = max(res, dp[2][i]);
            }
    }

    cout << res << endl;

    return 0;
}