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

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

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

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n+1];
        int[] dp = new int[n+1];
        dp[1] = 1;

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

        int answer = dp[0];
        for(int i=1; i<=n; i++){
            int max = 0;
            for(int j=i-1; j>=0; j--){
                if(arr[j] < arr[i] && dp[j] > max) max = dp[j];
            }
            dp[i] = max + 1;
            answer = Math.max(answer, dp[i]);
        }
        System.out.println(answer);

        Stack<Integer> stack = new Stack<>();
        for(int i=n; i>=1; i--){
            if(dp[i] == answer){
                stack.push(arr[i]);
                answer--;
            }
        }
        while(!stack.isEmpty()){
            System.out.print(stack.pop()+" ");
        }
    }
}

https://yeoncoding.tistory.com/597

[JAVA] 백준 11053번- 가장 긴 증가하는 부분 수열

 

 

11053 가장 긴 증가하는 부분 수열 문제에서 구한 최장길이의 수열의 길이만 출력하는게 아니라 수열도 나열해 출력해야 한다.

그러기 위해 가장 긴 수열의 길이를 1씩 감소시키며 dp 배열을 거꾸로 추적해나가며 arr의 원소들을 찾으면 된다. 

마지막에 증가하는 순으로 출력하기 위해 스택을 사용했다.