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

문제를 읽고 이해하기

수열 S가 어떤 수 S_k를 기준으로 S₁ < S₂ < ... 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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제 입력 1

10 1 5 2 1 4 3 4 5 2 1

예제 출력 1

7

재정의와 추상화

(바이토닉 수열이 무엇인지는 문제에 나와있으니 따로 설명하지 않겠습니다.)

예제 입력을 보면 10 1 5 2 1 4 3 4 5 2 1 의 원소를 가지는 수열의 부분수열 중 가장 긴 바이토닉 수열은 10 1 5 2 1 4 3 4 5 2 1 으로, 1 2 3 4 5 2 1 이다. 따라서 출력이 7이다.

이 예제를 통해 알 수 있듯이, 원소가 서로 인접한지는 상관 없이, 특정 원소 S_k를 기준으로 왼쪽에서 S₁ < S₂ < ... S_k-1 < S_k 을 만족하고 오른쪽에서 S_k > S_k+1 > ... S_N-1 > S_N를 만족하는 부분 수열 중 가장 긴 것을 찾는 것이 문제이다.

따라서 왼쪽과 오른쪽을 나누어 각각 동적 계획법(DP)를 적용한다. 점화식은 아래와 같다.

// 1 <= i < n
// 0 <= k <= i - 1
// arr[i] > arr[k]에 대해서
dp[i][왼쪽] = max(dp[k][왼쪽] + 1, dp[i][왼쪽])

// 0 <= i <= n - 2
// i + 1 <= k < n
// arr[i] > arr[k]에 대해서
dp[i][오른쪽] = max(dp[k][오른쪽] + 1, dp[i][오른쪽]);

• dp[i][방향] : i번째 원소에 대해 특정 방향에서 바이토닉 수열의 조건을 만족하는 부분 수열 중 가장 긴 수열의 길이

위 과정을 통해 왼쪽과 오른쪽 방향 각각에서 바이토닉 수열의 조건을 만족하는 가장 긴 수열의 길이를 찾았다면, 왼쪽에서의 값과 오른쪽에서의 값을 더한 후 + 1 한 것이 i번째 원소에 대해 양방향에서 바이토닉 수열의 조건을 만족하는 부분 수열 중 가장 긴 수열의 길이이다.

for (int i = 0; i < n; i++)
    values.push(dp[i][왼쪽] + dp[i][오른쪽] + 1);

코드 작성

#include <iostream>
#include <queue>
#include <utility>
using namespace std;

int arr[1001];
int dp[1001][2];
priority_queue<int> values;

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    for (int i = 1; i < n; i++) {
        for (int k = i - 1; k >= 0; k--) {
            if (arr[i] > arr[k]) {
                dp[i][0] = max(dp[k][0] + 1, dp[i][0]);
            }
        }
    }

    for (int i = n - 2; i >= 0; i--) {
        for (int k = i + 1; k < n; k++) {
            if (arr[i] > arr[k]) {
                dp[i][1] = max(dp[k][1] + 1, dp[i][1]);
            }
        }
    }

    for (int i = 0; i < n; i++)
        values.push(dp[i][0] + dp[i][1] + 1);

    cout << values.top();

    return 0;
}