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

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

문제

알고리즘 접근 방법

DP를 이용한다.

1. 왼쪽에서 부터 가장 긴 증가하는 수열을 구한다. -> 배열 a에 저장
2. 오른쪽에서부터 가장 긴 증가하는 수열을 구한다. -> 배열 b에 저장
3. 왼쪽 + 오른쪽 합친 것 중 가장 큰 수 - 1

풀이

#include <iostream>

using namespace std;

int main(){

    int A;

    cin >> A;

    int Ai[A+1] = {0,};

    for(int i=1; i<=A; i++)
        cin >> Ai[i];

    int a[A+1] = {1, };
    int b[A+1] = {1, };

    // dp[N] = 가장 긴 바이토닉 수열 
    // = [1~N-1] 까지 가장 긴 증가 부분 수열 + 1(N) + [N+1 ~ A] 까지 가장 긴 감소 부분 수열
    
    for(int i=1; i<=A; i++){
        a[i] = 1;
        for(int j=1; j<i; j++){
            if(Ai[j] < Ai[i]){
                a[i] = max(a[j]+1, a[i]);
            }
        }

    }

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

    int result = 0;
   for (int i=1; i<=A; i++){
       int sum = a[i] + b[i] - 1;
       if (result < sum)
            result = sum;
    }

    cout << result << endl;

    return 0;
}

정리

중간에 생각이 꼬여서 복잡해졌는데 그냥 생각한 거랑 같은 알고리즘..이었당

💡 참고 포스팅

snnchallenge님 블로그