BOJ 14002. 가장 긴 증가하는 부분수열 4(LIS)

BOJ 14002. 가장 긴 증가하는 부분수열 4 (LIS)

풀이

beomseok95.tistory.com/355 위 문제와 같은 문제이지만 LIS의 길이뿐 아니라 모든 원소를 출력해야한다.
위 LIS 문제와 같이 푸는데, 역추적을 위한 배열을 만들어 LIS에 연결되는 인덱스를 저장한다.

import java.io.IOException;
import java.util.Scanner;
import java.util.Stack;

class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        StringBuilder answer = new StringBuilder();
        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] d = new int[n]; // 길이를 담을 배열
        int[] v = new int[n]; // 경로를 추적할 인덱스를 담을 배열
        int max = -1;
        int index = -1;

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            d[i] = 1;
            v[i] = -1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && d[i] < d[j] + 1) {
                    d[i] = d[j] + 1;
                    v[i] = j;
                }
            }

            if (max < d[i]) {
                max = d[i];
                index = i;
            }
        }
        answer.append(max).append("\n");

        Stack<Integer> stack = new Stack<Integer>();
        while (index != -1) {
            stack.push(arr[index]);
            index = v[index];
        }

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

        sc.close();
        System.out.println(answer);
    }
}

import java.util.*

fun main() {
    val n = readLine()!!.toInt()
    val arr = readLine()!!.split(" ").map { it.toInt() }
    val d = IntArray(n) { 1 } // 길이를 담을 배열
    val v = IntArray(n) { -1 } // 경로를 추적할 인덱스를 담을 배열

    for (i in 0 until n) {
        for (j in 0 until i) {
            if (arr[i] > arr[j] && d[i] < d[j] + 1) {
                d[i] = d[j] + 1
                v[i] = j
            }
        }
    }
    val maxLength = d.maxOf { it }
    var index = d.indexOf(maxLength)
    println(maxLength)

    val stack = Stack<Int>()
    while (index != -1) {
        stack.push(arr[index])
        index = v[index]
    }

    while (!stack.isEmpty()) {
        print("${stack.pop()} ")
    }
}

풀이소스

github.com/beomjo/algorithm-study/commit/2927f0207bb85c7dce70681a1aecef2d41903a2d