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

링크

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다.
그러한 수열이 여러가지인 경우 아무거나 출력한다.

풀이

이전 문제 가장 긴 증가하는 부분 수열과 같이 DP를 사용한다.

수열에서 어떠한 수(x)는 왼쪽에 위치한 수들과 비교해 큰 경우 "증가하는 부분 수열"을 이룰 수 있다.

이때, "가장 긴" 증가하는 부분 수열을 찾아야 하므로 왼쪽에 위치한 수들 중 "가장 길고, 어떠한 수(x)보다 작은" 수을 찾아 연결해야 한다.

그림에서 30은 10, 20, 10과 부분수열을 이룰 수 있다.
그리고 20은 10과 부분수열을 이룰 수 있다.
30을 기준으로 10-20-30이 "가장 긴 증가하는 부분수열"이다.

아래의 패턴을 반복하면 특정 수(x) 기준 가장 긴 증가하는 부분 수열을 찾을 수 있다.
1. 왼쪽의 수들 중 특정 수(x) 보다 작은 수(y)를 찾는다.
2. 작은 수(y)들 중 가장 긴 수열을 찾는다.
3. 가장 긴 수열을 찾기 위해 작은 수(y)를 기준으로 1, 2를 반복한다.

그러나 위의 패턴은 부분 수열의 마지막 값(최대값)을 알아야한다.
최대값을 모르는 경우 특정 수가 바뀌므로, 이전에 했던 작업을 다시 수행해야한다.

이를 배열에 값을 저장하는 방법으로 해결할 수 있다.
인덱스와, 값, 값이 포함된 수열의 이전 인덱스, 수열의 길이를 저장하는 배열을 선언한다.
각 수는 자기자신이 부분 수열을 이루며, 이전 수의 인덱스를 자기 인덱스로 한다.

1번 인덱스부터 시작해 5번 인덱스까지 왼쪽의 수들과 비교해 값을 채운다.
1. 왼쪽 수의 값이 작아야 한다.
2. 왼쪽 수의 부분 수열의 길이가 같거나 커야한다.

1,2번을 만족하는 경우 이전 수의 인덱스를 왼쪽 수의 인덱스로 채우고,
부분 수열의 길이를 왼쪽 수의 부분 수열의 길이 값+1로 저장한다.

마지막 인덱스까지 비교한 후, 부분 수열의 길이 중 가장 큰 값을 출력한다.
그리고, 가장 큰 값의 이전 수의 인덱스를 이용해 역으로 값을 출력한다.

20(1: 괄호 안 숫자는 인덱스 번호)과 왼쪽 숫자 비교
10(0)과 비교시 1,2번 조건을 만족하므로 20(1)의 이전 수 인덱스와 부분 수열의 길이를 수정한다.

10(2)과 왼쪽 숫자 비교
왼쪽 숫자들과 비교시 조건을 만족하는 숫자가 없으므로 수정하지 않는다.

30(3)과 왼쪽 숫자 비교
10(0), 20(1)과 비교시 1,2번 조건을 만족하므로 30(3)의 이전 수 인덱스와 부분 수열의 길이를 수정한다.

20(4)과 왼쪽 숫자 비교
10(0), 10(2)과 비교시 1,2번 조건을 만족하므로 20(4)의 이전 수 인덱스와 부분 수열의 길이를 수정한다.

50(5)과 왼쪽 숫자 비교
10(0), 20(2), 30(3)과 비교시 1,2번 조건을 만족하므로 50(5)의 이전 수 인덱스와 부분 수열의 길이를 수정한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        // input | N -> int, stk -> stringToken
        int N = Integer.parseInt(br.readLine());
        StringTokenizer stk = new StringTokenizer(br.readLine());

        /** init | Ai = int[N][3]
         * [][0]: 수열
         * [][1]: 길이
         * [][2]: 이전 수(인덱스)
         */
        int[][] Ai = new int[N][3];
        for(int i=0; i<N; i++){
            Ai[i][0] = Integer.parseInt(stk.nextToken());
            Ai[i][1] = 1;
            Ai[i][2] = i;
        }

        // solve
        // len: 가장 긴 수열의 길이
        // index: 가장 긴 수열의 마지막 인덱스
        int len = 1; 
        int index = 0;
        //loop | 왼쪽 수들과 비교 
        for(int i=1; i<N; i++){
            for(int j=0; j<i; j++){
                if(Ai[j][0]<Ai[i][0] && Ai[j][1]>=Ai[i][1]){
                    Ai[i][1] = Ai[j][1]+1;
                    Ai[i][2] = j;

                    if(Ai[i][1]>len){
                        len = Ai[i][1];
                        index = i;
                    }
                }
            }
        }

        // make indexs | 
        int[] indexs = new int[len];
        for(int i=len-1; i>=0; i--){
            indexs[i] = index;
            index = Ai[index][2];
        }


        // print
        String answer = "";
        for(int i=0; i<len; i++)
            answer +=  Ai[indexs[i]][0] + " ";
        
        System.out.println(len);
        System.out.println(answer);
    }
}