[BOJ 14002] 가장 긴 증가하는 부분 수열 (Java, DP, LIS)

 

 

---

문제 링크 

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

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

---

문제 풀이 

- 시간 복잡도 : O(N^2)

- "병사 배치하기" 문제에서 역추적을 추가한 문제

- Stack의 성질(LIFO)을 활용하게 되면 pop하는 것만으로도 오름차순 정렬 결과를 구할 수 있다 

 

https://dev-ljw1126.tistory.com/271

[BOJ 18353] 병사 배치하기 (Java, DP, LIS)

---

제출 코드

import java.util.*;
import java.io.*;

public class Main {
    
  static StringBuilder sb = new StringBuilder();

    static int N;

    static int[] DP;

    static List<Integer> DATA = new ArrayList<>();
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            DATA.add(Integer.parseInt(st.nextToken()));
        }

        DP = new int[N];
        Arrays.fill(DP, 1);
    }

    static void pro() {
        for(int i = 1; i < N; i++) {
            for(int j = 0; j < i; j++) {
                if(DATA.get(i) > DATA.get(j)) {
                    DP[i] = Math.max(DP[i], DP[j] + 1);
                }
            }
        }

        int maxValue = Arrays.stream(DP).max().getAsInt();
        sb.append(maxValue).append("\n");

        Stack<Integer> stack = new Stack<>();
        for(int i = N - 1; i >= 0; i--) {
            if(maxValue < 0) break;
            if(DP[i] == maxValue) {
                stack.add(DATA.get(i));
                maxValue -= 1;
            }
        }

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

        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}