[BOJ/백준][Gold4] 14002 : 가장 긴 증가하는 부분수열 4 (C++)

www.acmicpc.net/problem/14002

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

 

 

[난이도] Gold4

[유형] DP (LIS)

 

[풀이]

d[i] = i번째 수로 끝나면서 가장 긴 증가하는 부분수열의 길이

prev[i] = i번째 수로 끝나면서 가장 긴 증가하는 부분수열에서 i번째 앞의수 위의 두가지를 이용해서 구한다.

#include <cstdio>
int N,a[1001],d[1001],prev[1001];
void prt(int n){
    if(n==0) return;
    prt(prev[n]);
    printf("%d ",a[n]);
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    for(int i=1;i<=N;i++){
        for(int j=0;j<i;j++){
            if(a[j]<a[i]) {
                if(d[i]<d[j]+1){
                   d[i]=d[j]+1;
                   prev[i]=j;
                }
            }
        }
    }
    int mxi=0,mxV=0;
    for(int i=1;i<=N;i++) {
        if(d[i] > mxV){
            mxi=i;
            mxV=d[i];
        }
    }
    printf("%d\n",mxV);
    prt(mxi);
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/14002.cpp