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

 

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

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

 

#문제 간단 정리

가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053문제에서 한단계 더 나아간 문제이다

주요 로직은 이 문제를 참고하도록 하자

11053번: 가장 긴 증가하는 부분 수열

#문제 해결 방법

 

이전 문제에서 증가하는 수열은 한쪽으로 증가하는 수열을 찾았는데

바이토닉 부분수열은 증가하다가 감소하는 부분을 합쳤다.

 

감소하는 부분수열은 반대로보면 오른쪽에서부터 증가하는 수열이기 때문에

좌로부터 증가하는 수열

그리고 우로부터 증가하는 수열을 dp로 갱신해 준 뒤에

두 dp 배열을 합해서 -1 한 길이가 바이토닉 수열의 길이다.

그러므로 

좌 + 우 -1 해준

바이토닉 부분수열의 최대길이를 찾았다.

 

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

typedef long long ll;

int main() {
    
    int N;
    cin >> N;

    vector<int> seq(N + 1,0);
    for (int i = 1; i <= N; i++) {
        cin >> seq[i];
    }


    //우로 증가하는 수열 길이
    vector<int> d(N + 1, 1);
    for (int i = 1; i <= N; i++) {
        d[i] = 1;

        for (int j = 1; j < i; j++) {
            if (seq[j] < seq[i] && d[i] < d[j] + 1) {
                d[i] = d[j]+1;
            }
        }
    }

    //좌로 증가하는 수열 길이
    vector<int> p(N + 1, 1);
    for (int i = N; i >=1 ; i--) {
        p[i] = 1;

        for (int j = N; j > i; j--) {
            if (seq[j] < seq[i] && p[i] < p[j] + 1) {
                p[i] = p[j] + 1;
            }
        }
    }
    
    int maxLen = 1;

    for (int i = 1; i <= N; i++) {
        maxLen = max(d[i] + p[i] - 1, maxLen);
    }
    cout << maxLen << "\n";

    return 0;
}