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

문제

풀이

설명

가장 긴 증가하는 부분수열에서 해당 수열까지 출력하는 문제이다.

앞에서 알아야 했던 A[i], D[i] 말고도 V[i]까지 구해야 한다.
V[i] = A[i]의 앞에 와야 하는 수의 인덱스 이다.
즉, A[i]의 앞에는 A[V[i]]가 와야 길이가 가장 길다.

코드

import java.util.Scanner;

public class Num14002 {
	static int[] a;
    static int[] d;
    static int[] v;
    static void go(int p) {
        if (p == -1) return;
        go(v[p]);
        System.out.print(a[p] + " ");
    }

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
        int n = sc.nextInt();
        a = new int[n];
        
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        
        d = new int[n];
        v = new int[n];
        
        for (int i=0; i<n; i++) {
            d[i] = 1;
            v[i] = -1;
            for (int j=0; j<i; j++) {
                if (a[j] < a[i] && d[i] < d[j]+1) {
                    d[i] = d[j]+1;
                    v[i] = j;
                }
            }
        }
        
        int ans = d[0];
        int p = 0;
        
        for (int i=0; i<n; i++) {
            if (ans < d[i]) {
                ans = d[i];
                p = i;
            }
        }
        System.out.println(ans);
        go(p);
        System.out.println();
	}

}

코드설명

참고 :
출처 : https://www.acmicpc.net/problem/14002