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

생각 정리

D[n] = 수열의 n번째 요소까지 가장 긴 증가하는 부분 수열의 길이
S[n] = 주어진 수열의 n번째 요소

단순하게 D[n]이 업데이트될 때의 수열의 n번째 요소들을 따로 저장하면 될 것이라고 생각했다.
골드인데 금방 풀수있을거 같아 !!!! 라고할뻔

생각하지 못한 것

D[n]이 업데이트될 때는 S[1]~S[n-1] 까지의 숫자들과 S[n]를 비교해서 S[n]보다 S[i]가 작을 때 D[n]을 업데이트한다.
그러니, 같은 S[n]이 여러번 나올 수 있다는 것이다.

검색을 해보았고,

가장 긴 증가하는 부분 수열을 출력할 때는 D[n]의 최장길이, S배열, D배열을 가지고 추적하며 구해갔다.

❓ 왜 D[1]이 아닌 D[n]부터 구하는 것일까?

• D[i-1]과 D[i]의 값이 같다면 거꾸로 탐색했을 때 S[i]이 S[i-1]보다 더 작은 수이기 때문이다.
• S[i-1] < S[i]이었다면 D[i-1]과 D[i]의 값이 같지 않았을 것이다.
• 즉, D[i]의 값과 D[j]의 값이 같다면 i < j일 때 S[i] > S[j]가 된다고 이해했다.

for(int i=n; i>0; i--)
	if(D[i] == max) {
    	//이때의 S[i]가 수열의 max번째 수이다.
    	max --;
    }

n부터 구하기 때문에 오름차순이 아닌 내림차순의 형태로 수열의 값을 구하게되고, 오름차순으로 나타내기 위해 stack을 사용한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
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[] S = new int[n+1];
        int[] D = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++)
            S[i] = Integer.parseInt(st.nextToken());
        
        D[1] = 1;
        int max = 1;
        for(int i=2; i<=n; i++) {
            D[i] = 1;
            for(int j=1; j<i; j++) {
                if(S[j] < S[i] && D[i] < D[j] + 1)
                    D[i] = D[j] + 1;
            }
            max = Math.max(max, D[i]);
        }


        System.out.println(max);
      
        Stack<Integer> stack = new Stack<>();

        // D[i]의 값이 같다면 거꾸로 탐색했을 때 먼저 나오는 값이 더 작은 수
        // 왜냐하면 값이 더 컸다면, D[i]의 값이 작지 않았을 것이다.
    
        for(int j=n; j>0; j--){
            if(D[j] == max){
                stack.push(S[j]);
                max--;
            }
        }

       while(!stack.isEmpty())
            System.out.print(stack.pop() + " ");
    }
}