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

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

난이도

골드4

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

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

내 코드

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

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

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

        ArrayList<Integer>[] dpList = new ArrayList[N];
        dpList[0] = new ArrayList<>();
        dpList[0].add(nums[0]);

        for (int i = 1; i < N; i++) {
            int maxCnt = 0;
            int idx = -1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (maxCnt < dpList[j].size()) {
                        maxCnt = dpList[j].size();
                        idx = j;
                    }
                }
            }
            if (idx == -1) {
                dpList[i] = new ArrayList<>();
            } else {
                dpList[i] = new ArrayList<>(dpList[idx]);
            }
            dpList[i].add(nums[i]);
        }

        int maxLength = 0;
        int maxIndex = 0;
        for (int i = 0; i < N; i++) {
            if (dpList[i].size() > maxLength) {
                maxLength = dpList[i].size();
                maxIndex = i;
            }
        }
        
        System.out.println(maxLength);
        for (int k : dpList[maxIndex]) {
            System.out.print(k + " ");
        }
    }
}

연속되는 수열의 값을 저장하는 ArrayList로 DP 배열을 생성했다.

이중 for문을 통해서 현재 인덱스(i) 기준, 앞에 있는 인덱스(j)들 중에서 값이 더 크고, 배열의 크기가 가장 큰 인덱스를 저장한다.

만약 현재 값이 가장 작다면, 저장된 인덱스가 없을테니 새로운 배열을 선언해서 DP 배열에 넣어주고, 아니라면 찾은 인덱스의 배열을 찾아서 넣어준다. 두 가지 경우 모두 현재의 값을 배열에 넣어줘야 한다.

그러면 DP 배열은 각 위치에서 증가하는 값들을 리스트로 저장해서 가지고 있기 때문에, 그 중 배열의 크기가 가장 큰 인덱스를 찾아서 출력하면 된다.