Boj 11054 c++ 가장 긴 바이토닉 부분 수열

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

 

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

 

LIS 유형의 문제이다. 이전에는 가장 긴 증가하는 부분수열, 가장 긴 감소하는 부분수열과 같은 것들을 구했다면 이번에는 증가하다가 전환점에서 다시 감소하는 부분수열의 길이의 최댓값을 구하는 것이다.

 

중간에서 꺾이는 지점을 어떻게 처리할까 고민이 될 수도 있지만, 오른쪽 인덱스 기준의 LIS의 길이와 왼쪽 인덱스 기준의 LIS길이를 구한 후, 두 dp배열의 값의 합 - 1이 가장 큰 지점의 값을 출력하면 해결된다.

 

하지만 길이가 1인 수열의 경우, 바이토닉 수열의 길이 또한 1이므로, 이를 예외처리 해주어야 한다.

 

LIS에 대한 유연한 사고가 요구되는 문제였다.

 

전체코드

 

#include <iostream>
using namespace std;

int arr[1001];
int ldp[1001];
int rdp[1001];

int main() {

    int n, ans = 0;
    cin >> n;

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

    for(int i = 1; i < n; i++) {
        ldp[i] = 1;
        for(int j = i-1; j >= 1; j--) {
            if(arr[i] > arr[j]) {
                ldp[i] = max(ldp[i], ldp[j]+1);
            }
        }
    }
    for(int i = n; i >= 1; i--) {
        rdp[i] = 1;
        for(int j = i+1; j <= n; j++) {
            if(arr[i] > arr[j]) {
                rdp[i] = max(rdp[i], rdp[j]+1);
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        ans = max(ans, rdp[i] + ldp[i]);
    }
    if(n == 1){
        cout << 1;
        return 0;
    }
    cout << ans-1;
}