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

1. 문제

11054번: 가장 긴 바이토닉 부분 수열 (acmicpc.net)

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

 

2. 풀이

한 지점에서 왼쪽에선 증가하고 오른쪽에선 감소하는 가장 긴 수열의 길이를 찾는 문제이다.

 

각 지점에서 시작하는 수열중 가장 긴 증가(감소) 수열의 길이를 찾아서

 

두 수열의 길이를 더한 뒤 -1 을 해주면 답이된다(중심이되는 지점은 중복되므로 -1해줘야한다.)

 

즉 이문제는 lis를 두번 구하면 된다는 것이다.

 

한지점에서의 오른쪽 감소 수열은 다음과 같이 두가지 부분 문제로 이루어져있다.

 

1. 만약 다음 번 숫자가 더 작을 경우 => 이 숫자를 시작으로하는 최대 수열 + 1

2. 지금 숫자가 무엇이든간에 다음 숫자로 넘어가는 경우

 

이러한 과정을 재귀적으로 표현한게 아래와 같은 코드이다.

 

이와 반대 방향인 왼쪽 증가 수열은 이것의 반대과정이므로 간단하게 똑같은 함수로 최대 수열을 구할 수 있다.

 

 

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <numeric>
 
using namespace std;
int N;
int dec1[1002][1001], inc[1002][1001];
vector<int> v;
 
int initial(int idx, int num, int a[1002][1001], int idxControl) {
    if(idx == -1 || idx == N) {
        return 0;
    }
    int& ret = a[num][idx];
    if(ret != -1) {
        return ret;
    }
    
    if(num > v[idx])
        ret = initial(idx + idxControl, v[idx], a, idxControl) + 1;
    if(num != 1001)
        ret = max(ret, initial(idx + idxControl, num, a, idxControl));
    return ret;
}
//10
//1 5 2 1 4 3 4 5 2 1
 
int main() {
    cin>>N;
    v = vector<int>(N);
    for(int i = 0; i < N; i++) {
        cin>>v[i];
    }
 
    memset(dec1, -1, sizeof dec1);
    memset(inc, -1, sizeof inc);
 
    int m = 0;
    for(int i = N-1; i >= 0; i--) {
        initial(i, 1001, inc, -1);
        initial(i, 1001, dec1, 1);
        if(m < inc[1001][i] + dec1[1001][i]) {
            m = inc[1001][i] + dec1[1001][i];
        }
    }
    
    cout<<m-1;
}