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

문제

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

풀이

LIS(Longest Increasing Subsequence) 알고리즘의 응용 버전이었다.

LIS 알고리즘의 경우, $O(NlogN)$ 복잡도를 띄는 이진탐색을 활용한 로직이 가장 최적화된
형태이다. 하지만, 이 문제에선 LIS 배열을 복원해야 하는 조건이 있고 최악의 경우가 $N=1,000$이므로 $O(N^2)$ 복잡도의 로직을 사용하는 것이 수월하다.

2 x n 형태의 dp 배열을 이용해 풀이했다. dp[0][i]값은 i까지의 LIS 길이를 의미한다. dp[1][i]의 값은 dp[0][i]길이의 LIS 배열 내에서 i이전 요소의 인덱스를 저장한다. 0..i * 1..j로 반복문을 돌며 LIS 길이(dp[0][i])가 갱신될 때 dp[1][i]도 갱신해준다. 이후 dp[1][i]의 값을 역탐색해 LIS 배열을 복원할 수 있다. LIS 배열을 반대로 탐색하므로 값을 출력하기 위해 LIFO 구조의 스택을 이용했다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int[][] dp = new int[2][n];
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = -1;
            dp[1][i] = 1;
        }

        int maxLength = 1;
        int index = 0;

        for (int i = 1; i < dp[0].length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    if (dp[1][i] < dp[1][j] + 1) {
                        dp[1][i] = dp[1][j] + 1;
                        dp[0][i] = j;
                    }
                }
            }

            if (maxLength < dp[1][i]) {
                maxLength = dp[1][i];
                index = i;
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(maxLength).append("\n");

        Stack<Integer> stack = new Stack<>();
        while (index >= 0) {
            stack.push(arr[index]);
            index = dp[0][index];
        }

        while (!stack.isEmpty()) {
            sb.append(stack.pop()).append(" ");
        }

        System.out.print(sb);
        br.close();
    }
}

결과