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

문제 URL

https://www.acmicpc.net/problem/14002

나의 풀이

package backjoon;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n + 1]; // 수열
        int[] d = new int[n + 1]; // i번째까지 가장긴 증가하는 부분수열의 길이
        StringBuilder[] sb = new StringBuilder[n + 1]; // i번쨰의 부분수열
        StringTokenizer str = new StringTokenizer(br.readLine());

        for (int i = 1; i <= n; i++)
            sb[i] = new StringBuilder("");

        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(str.nextToken());
            int idx = -1;
            for (int j = 1; j <= i - 1; j++) {
                if (d[i] < d[j] && a[j] < a[i]) {
                    d[i] = d[j];
                    idx = j;
                }
            }
            d[i] += 1;
            if(idx != -1 && sb[idx].length()>0)
                sb[i].append(sb[idx] + " ");
            sb[i].append(a[i]);
        }

        int max = -1;
        int idx = -1;
        for (int i = 1; i <= n; i++) {
            if (max < d[i]) {
                max = d[i];
                idx = i;
            }
        }
        System.out.println(d[idx]);
        System.out.println(sb[idx]);
    }
}

다른 풀이 **

import java.util.*;

public class Main {
    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();
    }
}

느낀점

동적계획법 을 이용한 문제다.

출처) 백준 기초1 강의

V[i] = A[i]의 앞에 와야하는 수의 인덱스. 즉, A[i]의 앞에는 A[V[i]]가 와야 길이가 가장길다.

역추적 하는 방법 기억하자!!!