[백준] 열차정렬(4198)

문제 링크 : [백준] 열차정렬(4198)

문제 설명

n개의 서로다른 수로 이루어진 수열이 주어 질 때, 새로운 배열에 차례대로 수를 왼쪽에 붙이거나, 오른쪽에 붙이거나, 버리는 세가지 경우를 행하여, 만들 수 있는 수열 중 가장 긴 수열의 길이를 출력하세요.

입력

N(행렬의 길이, 1<=N<=2,000)
D_i(i번째 수열의 수, 서로 모두 다름, 문제에는 빠져있으나, int 범위내로 가정하고 풀었을때 풀렸습니다.)

3
1
2
3

출력

가장 긴 수열의 길이

3

카테고리

#DP #LIS

시간 복잡도 상한

O(N²logN)

해결 방법

1. 한 위치를 기준으로 가장 긴 증가하는 부분 수열(LIS)와 가장 긴 감소하는 부분 수열(LDS)를 구하면 되는 문제입니다.
2. 단, 일반적인 LIS와는 다르게, LIS와 LDS의 시작지점이 같아야 합니다.
3. 부분 수열들의 시작점을 고정해야되기 때문에, 인덱스의 진행은 역순으로 하는 것이 좋습니다.

시간복잡도

O(N²)

코드

#include<cstdio>
#include<algorithm>
using namespace std;
int n,d[2000],e[2000],f[2000],i,j,a;
int main(){
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",d+i);
    for(i=n-1;i>=0;i--){
        for(j=i+1;j<n;j++){
            if(d[j]>d[i])e[i]=max(e[j],e[i]);
            else f[i]=max(f[j],f[i]);
        }
        e[i]++;f[i]++;
        a=max(a,e[i]+f[i]-1);
    }
    printf("%d",a);
}