[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 14002

주어진 수열 내에서 증가하는 부분수열 LIS 중 최대길이와 그 수열 구하기

 

- 주어진 수열 a[]와 수열의 i번째 수까지의 LIS 최대길이를 저장하는 d[]를 생성

- i번째 수가 LIS가 성립하도록 영향을 준 수열의 인덱스를 v[i]에 저장함

- 부분수열이 존재하지 않을 때의 기본값인 1로 d[]를 초기화함

- 2부터 수열의 길이 n까지 반복하여 d[]에 값을 저장한다.

 

- 인덱스 i 이하인 수 j 중에서 a[i]보다 크면서, d[i]-1보다 큰 d[j]를 찾으면 d[i]=d[j]+1 로 업데이트한다.

- 이때, v[i]에 인덱스 j를 저장한다.

 

- 저장된 d[] 에서 최대값이 존재하는 LIS의 최대길이이다.

- d[]의 최대값을 가진 수의 인덱스를 ansIndex에 저장하고, a[ansIndex]를 stack에 저장한다.

- ansIndex를 v[ansIndex]로 갱신하며 스택에 저장하고, 수열이 끝나면 스택을 pop한다.

 

import java.util.Scanner;
import java.util.Stack;

public class BOJ14002 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n + 1];
        int d[] = new int[n + 1];
        int v[]=new int[n+1];
        Stack<Integer> st=new Stack<>();
        int ans=d[1];

        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            d[i] = 1;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = i - 1; j >= 1; j--) {
                if (a[i] > a[j] && d[i] < d[j] + 1) {
                    d[i] = d[j] + 1;
                    v[i]=j;
                }
            }
        }
        int ansIndex=1;
        for(int i=1;i<=n;i++) {
            if (ans < d[i]) {
                ans = d[i];
                ansIndex = i;
            }
        }
        System.out.println(ans);
        while(ansIndex>0){
            st.push(a[ansIndex]);
            ansIndex=v[ansIndex];
        }
        while(!st.empty())
            System.out.print(st.pop()+" ");

    }
}