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

#문제

www.acmicpc.net/problem/11054

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

#풀이 & 학습한 내용

가장 긴 증가/감소하는 부분 수열 문제를 응용한 문제이다. 먼저 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN에서 Sk에 for문을 통해 수열에 있는 모든 수를 넣어준다. 이때의 시간복잡도는 O(N).

 

그리고 Sk기준으로 수열의 앞부분에서는 Sk를 포함하는 가장 긴 증가하는 부분 수열을 구하고, 수열의 뒷부분에서는 Sk를 포함하는 가장 긴 감소하는 부분 수열을 구하면 된다. 이때, idp[j]는 j를 부분수열의 마지막으로 가질때의 증가하는 최대길이라 하고, ddp[j]는 j를 부분수열의 처음으로 가질때의 감소하는 최대길이로 정의한다.

 

idp는 앞부분부터 살펴보지만, ddp는 뒷부분부터 살펴봐야한다는 점을 기억하자. i가 0부터 N까지 일때의 idp[i]+ddp[i]-1 중 최댓값을 답으로 출력한다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int p[1002];
int idp[1002];
int ddp[1002];
 
int main(void) {
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> p[i];
    }
    
    int max = -1;
 
    //i = Middle Choice
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
            idp[j] = 1;
            for (int k = 1; k <= j; k++) {
                if (p[k]<p[j] && idp[k] + 1 > idp[j])
                    idp[j] = idp[k] + 1;
            }
        }//idp[j]는 j를 부분수열의 마지막으로 가질때의 최대길이
 
        for (int j = N; j >= i; j--) {
            ddp[j] = 1;
            for (int k = N; k >= j; k--) {
                if (p[k] < p[j] && ddp[k] + 1 > ddp[j])
                    ddp[j] = ddp[k] + 1;
            }
        }//ddp[j]는 j를 부분수열의 처음으로 가질때의 최대길이
 
        if (max < idp[i] + ddp[i] - 1)
            max = idp[i] + ddp[i] - 1;
    }
 
    cout << max << '\n';
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_11054.cpp

HoYoungChun/BOJ_algorithm