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

[14002] 가장 긴 증가하는 부분 수열 4 : http://boj.kr/14002

< 소스코드 >

lis(s) : s 번째에서 시작하는 가장 긴 증가하는 부분 수열 

#include <stdio.h>
#include <string.h>
 
int n;
int a[1001], d[1001];
int next[1001];
 
int lis(int s)
{
    int ret=0;
 
    if(d[s]) return d[s];
 
    for(int i=s+1; i<n; i++) {
        if(a[s] < a[i]) {
            int cur = lis(i);
            if(ret < cur) {
                ret = cur;
                next[s] = i;
            }
        }
    }
    return d[s] = ret+1;
}
 
void path(int k)
{
    if(k == -1) return ;
    printf("%d ", a[k]);
    path(next[k]);
}
 
 
int main()
{
    int k, ans=0;
    scanf("%d", &n);
 
    for(int i=0; i<n; i++)
        scanf("%d", a+i);
 
    memset(next, -1, sizeof(next));
 
    for(int i=0; i<n; i++) {
        int tmp = lis(i);
        if(ans < tmp) {
            ans = tmp;
            k = i;
        }
    }
 
    printf("%d\n", ans); 
    path(k);
    puts("");
 
    return 0;
}
 

>> next[i] 는 i의 다음 수열에 해당하는 인덱스.

>> n 제한이 1000 이라, O(n^2) 인 재귀로 가능하다.