[백준/JAVA] BOJ 14002 - 가장 긴 증가하는 부분 수열 4

dp인데 역추적을 곁들인...

👀 문제

14002번: 가장 긴 증가하는 부분 수열 4 ✨ 골드 4

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

예제 입력

6
10 20 10 30 20 50

예제 출력

4
10 20 30 50

🔑 키포인트

다이나믹 프로그래밍 역추적

✍️ 코드

📍 흔한 LIS 문제에 역추적이 추가된 문제
💡 배열에 이전 경로 저장하고, 스택 사용해서 역추적 해 주었다.

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

public class BOJ14002_가장긴증가하는부분수열4 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        dp[0] = 1;
        int answer = 1;
        int ans_idx = 0;
        for (int i = 1; i < n; i++) {
            int maxCnt = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[i] > arr[j]) {
                    if (dp[j] + 1 > maxCnt) {
                        maxCnt = dp[j] + 1;
                        root[i] = j;
                    }
                }
            }
            dp[i] = maxCnt;
            if (answer < dp[i]) {
                answer = dp[i];
                ans_idx = i;
            }
        }

        StringBuilder sb = new StringBuilder();
        Stack<Integer> stack = new Stack<>();
        sb.append(answer + "\n");

        while (stack.size() < answer) {
            stack.add(arr[ans_idx]);
            ans_idx = root[ans_idx];
        }
        while (!stack.isEmpty()) {
            sb.append(stack.pop() + " ");
        }
        System.out.println(sb.toString());
    }
}