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

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

가장 긴 증가하는 부분 수열 문제에서

DP결과를 저장하면서 저장하게 되는 결과가 나오게 근거 인덱스를 따로 만들어 저장합니다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int[] A = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        int[] D = new int[N];
        int[] V = new int[N];
        int max = 1;
        Arrays.fill(D, 1);
        Arrays.fill(V, -1);
        for (int i = 0; i < N; i++)
            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 idx = 0;
        for (int i = 0; i < N; i++)
            if (D[i] > max) {
                max = D[i];
                idx = i;
            }
        while (idx != -1) {
            sb.insert(0, A[idx] + " ");
            idx = V[idx];
        }
        System.out.println(max);
        System.out.print(sb);
    }
}