[백준] 가장 긴 증가하는 부분 수열 4 (14002번 JAVA) / 400 - 다이나믹 프로그래밍 1

[백준] 가장 긴 증가하는 부분 수열 4 (14002번 JAVA) / 400 - 다이나믹 프로그래밍 1

---

[접근 방법]

 

< 가장 긴 증가하는 부분 수열 (11053번 JAVA) > 문제에서 응용이 된 문제이다.

https://notorious.tistory.com/180

[백준] 400 - 다이나믹 프로그래밍 1 : 가장 긴 증가하는 부분 수열 (!) (11053번 JAVA)

 

기본적인 문제 풀이는 동일하고, LIS를 출력하는 것이 추가된 형태이다.

 

처음 고려한 방법은 "해당 원소를 마지막으로 하는 LIS의 길이" 를 저장한 배열 D에서 인덱스 0부터 N-1 까지 순차적으로 탐색하여, 1 부터 LIS의 길이 까지의 원소를 출력하면 된다고 생각하였다.

	StringBuilder sb = new StringBuilder();
        int a = 1;
        for(int i=0; i<N; i++){
            if(D[i] == a){
                sb.append(arr[i] + " ");
                a++;
            }
        }

위와 같은 코드를 입력하였다.

 

그러나 치명적인 반례가 있었다.

10
94 24 32 19 14 27 56 72 66 40

을 입력값으로 하면, 

4
94 32 56 72

와 같은 출력값이 발생하게 되었다.

 

그 이유는 arr의 첫 원소인 arr[0]는 D[0]으로 항상 1을 갖는다는 것이다.

 이는, 원소의 값이 가장 크던 가장 작던 상관 없이 출력하고자 하는 LIS에 포함된다는 뜻이다.

 

이를 해결하기 위해 D[]를 큰 인덱스 부터 역순 탐색하고, 발견한 원소값을 STACK에 담았다.

	// LIS의 길이
        int LIS_Length = LIS(arr, D);

        int a = LIS_Length;
        Stack<Integer> stack = new Stack<>();
        for(int i=N-1; i>=0; i--){
            if(D[i] == a){
                stack.push(arr[i]);
                a--;
            }
        }

---

[JAVA 코드]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main{

    public static int[] arr;
    public static int[] D;

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 1 <= N <= 1000
        int N = Integer.parseInt(br.readLine());

        arr = new int[N];

        // 해당 원소를 마지막으로 하는 LIS의 길이 저장
        D = new int[N];

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

        // LIS의 길이
        int LIS_Length = LIS(arr, D);

        int a = LIS_Length;
        Stack<Integer> stack = new Stack<>();

        // 역순으로 탐색
        for(int i=N-1; i>=0; i--){
            if(D[i] == a){
                stack.push(arr[i]);
                a--;
            }
        }

        // LIS의 길이
        bw.write(LIS_Length + "\n");

        // LIS 출력
        while(!stack.isEmpty()){
            bw.write(stack.pop() + " ");
        }

        bw.flush();
        bw.close();
    }

    public static int LIS(int[] arr, int[] D){

        int result = 0;

        for(int i=0; i<arr.length; i++){
            D[i] = 1;

            // INDEX = i 이전의 값 탐색
            for(int j=0; j<=i; j++){

                // 현재 원소보다 작음 and 현재 LIS의 길이 보다 큼 => 갱신
                if (arr[i] > arr[j] && D[j] + 1 > D[i]){
                    D[i] = D[j] + 1;
                }
            }

            if(D[i] > result){
                result = D[i];
            }
        }

        return result;
    }
}