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

문제

---

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

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

 

 

 

문제해결

---

- 11053 가장 긴 증가하는 수열 문제와 똑같이 가장 긴 수열 길이를 구하고 배열 역추적을 하면 된다

- 가장 긴 배열이 max라 했을때, dp 배열 뒤에서부터 검사하면서 max와 같은 경우를 stack에 담고 max를 -1 하면 된다

- 뒤에서 부터 검사하므로 LIFO 구조인 stack을 사용한다

import java.util.*;

public class B14002 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        // dp 배열 구하기
        int[] dp = new int[n];
        for (int i = 0; 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)
        int max = 0;
        for (int i : dp){
            max = Math.max(max, i);
        }
        System.out.println(max);
        //배열 역추적
        Stack<Integer> stack = new Stack<>();
        for (int i = n-1; i >= 0; i--) {
            if (max==dp[i]){
                stack.push(arr[i]);
                max--;
            }
        }

        while (!stack.isEmpty()){
            System.out.print(stack.pop() + " ");
        }
    }
}