[백준] 14002 가장 긴 증가하는 부분 수열 4

유명한 문제다!

근데 오랜만에 dp보다가 틀렸따!

 

먼저 dp식을 생각해보자

d[n] = n을 마지막으로 하는 가장 긴 수열로 생각하면 된다!

처음에 d[n]은 n까지 보면 가장 긴 길이라고 생각하다가 틀렸었다

 

n은 1000이기 때문에 그냥 for문을 돌면서 나를 기준으로 앞으로 가면서

나보다 작은수를 만날때마다 내 앞에 올수있는 것 중에서 나보다 길이가 긴 애를

가져가면 된다!

 

그럼 수열은 어떻게 구하면 될까?

stack을 타고간다는 생각으로 나는 내 앞에 오는 작은 수만 생각하면 된다

그럼 가장 긴 수열이 만들어졌을 때 계속 내 바로 앞 숫자만 호출하면 수열이 완성된다!

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int d[1010];
int a[1010];
int b[1010];
 
void print(int x){
    if(!b[x]) {
        printf("%d ",a[x]); return;
    }
    print(b[x]);
    printf("%d ",a[x]);
    
}
int main(){
    scanf(" %d",&n);
    for(int i=1;i<=n;i++) scanf(" %d",&a[i]);
    for(int i=1;i<=n;i++){
        d[i]=1;
        for(int j=i-1;j>=1;j--){
            if(a[i]>a[j] && d[i]<d[j]+1){
                d[i] = d[j]+1;
                b[i] = j;
            }
        }
    }
    int len=0,ans=0;
    for(int i=1;i<=n;i++) {
        if(len<d[i]){
            len=d[i]; ans=i;
        }
    }
    
    printf("%d\n",len);
    print(ans);
}