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

01 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/11054

나의 풀이

• left_DP[i]=l은 좌측부터 시작하는 부분 수열의 마지막 값이 A[i]인 증가하는 부분 수열의 길이가 l이라는 것을 의미한다.
• right_DP[i]=l은 우측부터 시작하는 부분 수열의 마지막 값이 A[i]인 증가하는 부분 수열의 길이가 l이라는 것을 의미한다.
• left_DP[i] + right_DP[i] - 1은 A[i] = S_k라고 할 때 가장 긴 바이토닉 부분 수열의 길이를 의미하게 된다.
  이 때 -1을 하는 이유는 left_DP[i]와 right_DP[i]를 구하는 과정에서 A[i]가 중복되기 때문이다.
• lefet_DP[i] + right_DP[i] - 1의 값 중 가장 큰 값을 찾으면 그 값이 답이다.

가장 긴 증가하는 부분 수열과 수열은 이전에 풀었던 가장 긴 감소하는 부분 수열와 동일하게 풀었다.

풀이 코드 : 11054 가장 긴 바이토닉 부분 수열

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int left_DP[1001];
int right_DP[1001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, num;
    vector<int> A;
    cin>>N;

    for(int i=0;i<N;i++){
        cin>>num;
        A.push_back(num);
        left_DP[i] = 1;
        right_DP[i] = 1;
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<=i;j++){
            if(A[j] < A[i]){
                left_DP[i] = max(left_DP[j]+1, left_DP[i]);
            }
        }
    }

    for(int i=N-1;i>=0;i--){
        for(int j=N-1;j>=i;j--){
            if(A[j] < A[i]){
                right_DP[i] = max(right_DP[j] + 1, right_DP[i]);
            }
        }
    }

    int answer = 0;
    for(int i=0;i<N;i++){
        if(answer < (left_DP[i] + right_DP[i]))
            answer = left_DP[i] + right_DP[i];
    }
    
    cout<<--answer;
}

채점결과