[BOJ 11054] 가장 긴 바이토닉 부분 수열

문제

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

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

 

---

풀이

DP를 사용합니다.

바이토닉 수열은 올라갔다 내려갈 수 있고, 올라가기만 할 수도 있으며, 내려가기만 할 수도 있습니다. 하지만, 내려갔다 올라갈 수는 없습니다. 그러므로, 두 가지 경우를 생각해 수열 \(A\)가 주어졌을 때 배열 \(dp\)를 다음과 같이 정의할 수 있습니다:

 

• \(dp[i][0]:\) \(A_{i}\)까지의 수열 중 바이토닉 부분 수열이 오름차순일 때 그 수열의 길이의 최대값.
• \(dp[i][1]:\) \(A_{i}\)까지의 수열 중 바이토닉 부분 수열이 내림차순이거나 한 번 올라갔다 내려가는 수열일 때 그 수열의 길이의 최대값.

그러므로 다음과 같이 점화식을 세울 수 있습니다:

$$dp[i][0] = \max\begin{cases}
1\\
\max_{j < i} dp[j][0] + 1,& \text{where}\ A_{j} < A_{i}
\end{cases}$$

$$dp[i][1] = \max\begin{cases}
1\\
1 + \max_{j < i} \max\begin{cases}
dp[j][0]\\
dp[j][1]
\end{cases}, &\text{where}\ A_{j} > A_{i}
\end{cases}$$

부분 수열은 어떤 곳에서도 끝날 수 있으므로 답은 \(\max_{i < N}\begin{cases}
dp[i][0]\\
dp[i][1]
\end{cases}\) 가 됩니다.

 

---

코드

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> input(N);
    vector<vector<int>> arr(N, vector<int>(2, 1));
    for (int i = 0; i < N; ++i) cin >> input[i];

    int mx = 1;
    for (int i = 1; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            if (input[j] < input[i] && arr[j][0] + 1 > arr[i][0])
                arr[i][0] = arr[j][0] + 1;
            else if (input[j] > input[i]) {
                if (arr[j][0] + 1 > arr[i][1])
                    arr[i][1] = arr[j][0] + 1;
                if (arr[j][1] + 1 > arr[i][1])
                    arr[i][1] = arr[j][1] + 1;
            }
            mx = max(mx, max(arr[i][0], arr[i][1]));
        }
    }

    cout << mx << "\n";

    return 0;
}