[백준] 11054번: 가장 긴 바이토닉 부분 수열 - C++

문제

수열 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를 이루고 있는 A_i가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ A_i ≤ 1,000)

 

출력

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

---

DP를 이용하여 풀 수 있는 문제. 역시나 앞의 문제들처럼 LIS 문제인데, 앞서 풀었던 문제들을 조금 응용하여 풀어야한다.

바이토닉 수열의 특징을 고려하여 길이가 N인 수열 A의 i번째 원소 A[i]를 기준으로 구해야 되는 것은 다음과 같다.

 

1. A[1]부터 A[i]까지의 가장 긴 증가하는 부분 수열의 길이

2. A[N]부터 A[i]까지의 역순으로 가장 긴 증가하는 부분 수열의 길이(A[i]부터 A[N]까지 가장 긴 감소하는 부분 수열의 길이)

 

1번과 2번을 각각 기록한 배열을 Increase[]와 Decrease[]라고 가정할 때, 두 배열의 원소별 합(Increase[i] + Decrease[i], 1 ≤ i ≤ N)을 구하여 합이 최댓값이 되는 경우가 가장 긴 바이토닉 부분 수열의 길이이다. 이 때 주의해야 할 점은 두 배열의 합으로 구한 최댓값에는 A[i]가 중복해서 들어간 경우이기 때문에 최댓값에 1을 빼준 값이 최종 최대 길이가 된다.

 

🔗 Increase() 함수와 Decrease() 함수의 기본 작동 원리 : 11053번 가장 긴 증가하는 부분 수열

코드

#include <cstdio>
#include <vector>

using namespace std;

vector<int> A;
vector<int> Increase(int n);
vector<int> Decrease(int n);
int sum(vector<int> Inc, vector<int> Dec);

int main(void) {
    int n;
    scanf("%d", &n);
    A.resize(n + 1);

    for(int i = 1; i <= n; i++) scanf("%d", &A[i]);
    printf("%d\n", sum(Increase(n), Decrease(n)));
    return 0;
}

vector<int> Increase(int n) {
    vector<int> Inc(n + 1);
    for(int i = 1; i <= n; i++) {
        Inc[i] = 1;
        for(int j = 1; j < i; j++) {
            if(A[i] > A[j] && Inc[i] < Inc[j] + 1) {
                Inc[i]++;
            }
        }
    }
    return Inc;
}

vector<int> Decrease(int n) {
    vector<int> Dec(n + 1);
    for(int i = n; i > 0; i--) {
        Dec[i] = 1;
        for(int j = n; j >= i; j--) {
            if(A[i] > A[j] && Dec[i] < Dec[j] + 1) {
                Dec[i]++;
            }
        }
    }

    return Dec;
}

int sum(vector<int> Inc, vector<int> Dec) {
    int max = 0;
    for(int i = 1; i < Inc.size(); i++) {
        max = (Inc[i] + Dec[i] > max ? Inc[i] + Dec[i] : max);
    }
    return max - 1;
}