[14002] 가장 긴 증가하는 부분 수열 4

문제 링크 : https://www.acmicpc.net/problem/14002

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

 

문제 해결 방법

DP를 이용한 LIS알고리즘으로 구현했다.

 

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] arr = new int[N + 1];
        int[] length = new int[N + 1];
        int max = 0;

        for (int i = 1; i <= N; i++) {
            arr[i] = sc.nextInt();
        }

        for(int i = 1; i <= N; i++) {
            length[i] = 1;
            for(int j = 0; j < i; j++){
                if(arr[i] > arr[j]){
                    length[i] = Math.max(length[i], length[j] + 1);
                    max = Math.max(max, length[i]);
                }
            }
        }

        Deque<Integer> q = new LinkedList<>();
        int idx = max;

        for(int i = N; i > 0; i--) {
            if (idx == length[i]) {
                q.push(arr[i]);
                idx--;
            }
        }

        System.out.println(max);
        while (!q.isEmpty()) {
            System.out.print(q.pop() + " ");
        }
    }
}