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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

포인트

유명한 LIS 문제이다. 길이만 구하는 것뿐만 아니라 그 부분 수열을 정확하게 구해야한다.

LIS 문제에는 2가지 알고리즘이 있다. 하나는 O(N^2) 시간복잡도를 갖고, 다른 하나는 O(N logN)의 시간 복잡도를 갖는다.

이 문제는 N의 범위가 1000이고 O(N^2)의 풀이로도 1초안에 수행할 수 있으므로 O(N^2)의 풀이로 해결하였다.

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

public class LIS_14002 {
    static int[] arr, dp;
    static int N;
    static Stack<Integer> stack = new Stack<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        dp = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = 1;
        int max = dp[0];
        for (int i = 1; i < N; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    max = Math.max(dp[i], max);
                }
            }
        }
        int ret = max;
        for (int i = N - 1; i >= 0; i--) {
            if(max == dp[i]) {
                stack.push(arr[i]);
                max--;
            }
        }
        while(!stack.isEmpty()) {
            sb.append(stack.pop()).append(" ");
        }
        bw.write(ret + "\n" + sb.toString() + "\n");

        bw.flush();
        bw.close();
    }
}

Stack을 이용해서 역추적할 수 있도록 했다.