[algorithm] 백준 - 가장 긴 바이토닉 부분 수열

이 문제는 DP로 가장 긴 증가하는 부분 수열과 관련된 문제이다.

 

daewoony.tistory.com/44

[algorithm] 백준 - 가장 긴 증가하는 부분 수열 1 & 4

증가하다가 감소하는 수열, 증가하는 수열, 감소하는 수열 모두 바이토닉 수열에 해당된다.

 

순서대로 반복문을 돌다가 현 위치의 수 부터 이전 수를 비교했을 때 현 위치의 수가 큰 수일 경우 값을 올리는 방식으로

가장 긴 증가하는 수열의 길이를 구하고,

 

그리고 거꾸로 반복문을 돌리면서 현 위치 수 부터 가장 끝 수까지를 비교했을 때 현 위치의 수가 큰 수일 경우 값을 올리는 방식으로

가장 긴 증가하는 수열  거꾸로 버전의 길이을 구한다.

 

 

예를 들면,

 

1 2 3 4 5 4 3 2 1 이라는 수열이 있다면,

 

가장 긴 증가하는 수열 거꾸로 버전으로 생각해보면,

1	2	3	4	5	4	3	2	1
1	2	3	4	5	4	3	2	1

그리고 가장 긴 증가하는 수열로 생각해보면,

1	2	3	4	5	4	3	2	1
1	2	3	4	5	4	3	2	1

 

합했을 때 가장 큰 수 - 1을 해주면 가장 긴 바이토닉 부분 수열의 길이를 구할 수 있다.

-1을 해주는 이유는 수가 하나 겹치기 때문에 -1을 해준다.

 

// 가장 긴 바이토닉 부분 수열
#include <iostream>
using namespace std;

int main(void){
    int count, answer = 1, arr[1001], dp[1001], rDp[1001];
    cin >> count;
    for(int i = 0; i < count; i++){
        cin >> arr[i];
        dp[i] = 1;
        for(int j = 0; j < i; j++){
            if(arr[i] > arr[j] && dp[i] <= dp[j]){
                dp[i] = dp[j] + 1;
            }
        }
    }
    for(int i = count - 1; i >= 0; i--){
        rDp[i] = 1;
        for(int j = count - 1; j > i; j--){
            if(arr[i] > arr[j] && rDp[i] <= rDp[j]){
                rDp[i] = rDp[j] + 1;
            }
        }
    }
    for(int i = 0; i < count; i++){
        answer = max(answer, dp[i] + rDp[i] - 1);
    }
    cout << answer;
}