백준 14002 (가장 긴 증가하는 부분수열 4) - java

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

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

전형적인 LIS를 구하는 문제이다. 길이는 dp를 활용하고 값을 구하기 위해서 별도의 past[] 배열을 선언하여 이전 값을 넣어주었다.

주의할점은 위의 LIS 문제는 이진 탐색을 사용하면 안된다는 것이다. 이진 탐색은 LIS의 길이는 정확히 알 수 있더라도 정확한 값을 알 수 는 없기 때문이다.

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

public class Main {
    static int n = 0;
    static int[] board;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        board = new int[n+1];
        int[] past = new int[n+1];

        st = new StringTokenizer(br.readLine(), " ");
        for(int i=1;i<=n;i++)
        {
            board[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[n+1];
        dp[1] = 1;
        past[1] = 1;

        int maxL = 1;
        for(int i=2;i<=n;i++){
            int max = 1;
            int idx = i;

            for(int j=i-1;j>=1;j--){

                if(board[i] > board[j])
                {
                    if(dp[j]+1 > max){
                        idx = j;
                    }
                    max = Math.max(max , dp[j] + 1);
                }

            }
            past[i] = idx;
            dp[i] = max;
            maxL = Math.max(maxL,dp[i]);
        }


        System.out.println(maxL);

        int maxIdx = 1;

        for(int i=1;i<=n;i++){
            if(dp[maxIdx] < dp[i]){
                maxIdx = i;
            }
        }
        Stack<Integer> stack = new Stack();
        while(true){
            stack.push(board[maxIdx]);

            if(maxIdx == past[maxIdx])
                break;

            maxIdx = past[maxIdx];

        }
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            sb.append(stack.pop()+" ");
        }
        sb.append("\n");
        System.out.println(sb);
        br.close();
    }
}