21.07.15 - [BOJ] 14002. 가장 긴 증가하는 부분 수열 4

[suhyunsim]

문제

• 14002

핵심 아이디어

• D[i] = A[1], ..., A[i]까지 수열이 있을 때 A[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이
• V[i] = A[i] 앞에 와야 하는 수의 인덱스. 즉 A[i]의 앞에는 A[V[i]]가 와야 길이가 가장 길다.
  • A[j], A[i] 순서 -> V[i] = j
• 재귀
• 표 그리는 방식을 그대로 구현
  

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q14002;

import java.util.Scanner;

public class Main {
    static int [] a;
    static int [] d;
    static int [] v;
    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();
    }

    private static void go(int p) {
        if (p == -1) return;
        go(v[p]);
        System.out.println(a[p] + " ");
    }
}