[백준 / Java] 14002: 가장 긴 증가하는 부분 수열 4 (DP)

난이도: Gold 4

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

 

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

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

 

아래 링크에 있는 문제를 응용한 문제이다.

이 문제를 먼저 풀어보고 해당 문제를 풀면 좀 더 쉽게 풀 수 있을 것이다.

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

 

위 링크에 있는 문제에서 가장 긴 증가하는 부분 수열의 길이를 구하려면 int 타입의 1차원 dp 배열을 만들어서 저장하고, 가장 큰 값을 출력하면 됐었다.

하지만 이번에는 부분 수열의 숫자도 일일히 다 구해야 한다.

그러려면 int 타입의 정수만 저장하는 배열로는 부족하다. 클래스를 따로 만들어서 클래스 타입의 배열을 만들어야 한다.

클래스는 다음과 같이 만들면 된다.

 

    static class Num {

        int now;        // 현재 수열 숫자

        int order;      // 수열 순서

        int beforeIdx;  // 현재 수열 숫자의 바로 이전 수열 숫자에 해당하는 인덱스

       

        Num(int now, int order, int beforeIdx) {

            this.now = now;

            this.order = order;

            this.beforeIdx = beforeIdx;

        }

    }

 

 

이 클래스 타입의 배열을 그림으로 표현하면 다음과 같다.

 

 

초기 세팅은 이러하다.

 

now(현재 수열 숫자): 입력받은 수열의 수 저장

order(수열 순서): 처음에는 모두 1로 초기화

beforeIdx(이전 수열 숫자 인덱스): 처음에는 모두 -1로 초기화

 

 

현재 인덱스(i): 1

비교하는 인덱스(j): 0

조건을 만족하므로 order를 1 증가하고, beforeIdx를 비교하는 인덱스로 변경하면 된다.

 

 

조건을 만족하므로 order를 1 증가하고, beforeIdx를 비교하는 인덱스로 변경했다.

비교하는 인덱스(j)는 현재 인덱스(i)의 - 1까지만 비교하므로, 현재 인덱스(i)를 다음 인덱스(i + 1)로 넘어가자.

 

 

현재 인덱스(i): 2

비교하는 인덱스(j): 0

조건을 만족하지 않으므로 아무것도 변경하지 않고 비교하는 인덱스를 다음으로 넘어간다.(j + 1)

 

현재 인덱스(i): 2

비교하는 인덱스(j): 1

조건을 만족하지 않으므로 아무것도 변경하지 않는다.

비교하는 인덱스(j)는 현재 인덱스(i)의 - 1까지만 비교하므로, 현재 인덱스(i)를 다음 인덱스(i + 1)로 넘어가자.

 

 

현재 인덱스(i): 3

비교하는 인덱스(j): 0

조건을 만족하므로 order를 1 증가하고, beforeIdx를 비교하는 인덱스로 변경하면 된다.

 

 

조건을 만족하므로 order를 1 증가하고, beforeIdx를 비교하는 인덱스로 변경했다.

비교하는 인덱스를 다음으로 넘어간다.(j + 1)

 

 

현재 인덱스(i): 3

비교하는 인덱스(j): 1

조건을 만족하므로 order를 1 증가하고, beforeIdx를 비교하는 인덱스로 변경하면 된다.

 

 

조건을 만족하므로 order를 1 증가하고, beforeIdx를 비교하는 인덱스로 변경했다.

비교하는 인덱스를 다음으로 넘어간다.(j + 1)

 

이와 같은 과정을 현재 인덱스(i)가 수열의 길이(N)가 될 때까지만 반복한다.

 

 

최종 결과는 이렇게 된다.

 

 

ArrayList<Integer> LIS = new ArrayList<>();

가장 긴 부분 수열(LIS)을 저장하는 ArrayList를 하나 만들고, order 중에 가장 큰 값이 담긴 인덱스를 찾는다. 여기서는 order의 최댓값이 4이므로, 가장 큰 값이 담긴 인덱스는 5이다.

 

해당 배열 값의 now는 50이므로 50을 저장한다. => LIS = { 50 }

그리고 해당 배열 값의 beforeIdx는 3이므로, 3으로 이동한다.

 

해당 배열 값의 now는 30이므로 30을 저장한다. => LIS = { 50, 30 }

그리고 해당 배열 값의 beforeIdx는 1이므로, 1로 이동한다.

 

해당 배열 값의 now는 20이므로 20을 저장한다. => LIS = { 50, 30, 20 }

그리고 해당 배열 값의 beforeIdx는 0이므로, 0으로 이동한다.

 

해당 배열 값의 now는 10이므로 10을 저장한다. => LIS = { 50, 30, 20, 10 }

그리고 해당 배열 값의 beforeIdx는 -1이므로 탐색을 종료한다.

 

마지막으로, 저장된 LIS를 역순으로 출력하면 답이 된다. => 10 20 30 50

 

 

주석에도 설명을 한 줄 한 줄 자세히 적어 놓았다.

자, 이제 코드를 보자.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class P14002_가장긴증가하는부분수열4 {
    static class Num {
        int now;        // 현재 수열 숫자
        int order;        // 수열 순서
        int beforeIdx;    // 현재 수열 숫자의 바로 이전 수열 숫자에 해당하는 인덱스
        
        Num(int now, int order, int beforeIdx) {
            this.now = now;
            this.order = order;
            this.beforeIdx = beforeIdx;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());    // 수열의 크기
        Num[] A = new Num[N];    // 수열 숫자, 수열 순서, 이전 수열 숫자 인덱스를 저장하는 1차원 배열
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int now = Integer.parseInt(st.nextToken());    // 현재 수열 숫자
            // now(현재 수열 숫자): 입력받은 수 저장
            // order(수열 순서): 처음에는 모두 1로 초기화
            // beforeIdx(이전 수열 숫자 인덱스): 처음에는 모두 -1로 초기화
            A[i] = new Num(now, 1, -1);
        }
        
        int maxIdx = 0;    // 가장 큰 값의 수열 순서(order)에 해당하는 인덱스
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++) {
                // 현재 숫자가 비교 숫자보다 크고, 현재 숫자의 순서가 비교 숫자의 순서 + 1보다 작다면
                if (A[j].now < A[i].now && A[j].order + 1 > A[i].order) {
                    A[i].order++;        // 현재 숫자의 순서 1 증가
                    A[i].beforeIdx = j;    // 이전 수열 숫자 인덱스를 비교 숫자로 바꾸기
                }
            }
            if (A[i].order > A[maxIdx].order) {    // 현재 숫자의 순서가 가장 큰 값의 수열 순서보다 크다면
                maxIdx = i;        // 가장 큰 값의 수열 순서 인덱스를 현재 숫자의 인덱스로 바꾸기
            }
        }
        
        ArrayList<Integer> LIS = new ArrayList<>();    // 가장 긴 증가하는 부분 수열을 저장하는 리스트
        int idx = maxIdx;    // 반복자: 가장 큰 값의 수열 순서(order)에 해당하는 인덱스
        
        while (true) {
            LIS.add(A[idx].now);    // 가장 긴 증가하는 부분 수열 리스트에 현재 숫자를 추가
            idx = A[idx].beforeIdx;    // 반복자를 이전 수열 숫자 인덱스로 변경
            if (idx == -1) {        // 이전 수열 숫자 인덱스가 -1이라면 수열 중 가장 작은 숫자
                break;                // 수열을 더 추가할 필요 없으므로 반복문 탈출
            }
        }
        
        // 가장 긴 증가하는 부분 수열의 길이 = 가장 큰 값의 수열 순서 출력
        bw.write(A[maxIdx].order + "\n");    
        
        // 가장 긴 증가하는 부분 수열을 저장하는 리스트를 역순으로 출력
        for (int i = LIS.size() - 1; i >= 0; i--) {
            bw.write(LIS.get(i) + " ");
        }
        
        bw.flush();        // bw.write()로 버퍼에 쌓았던 문자열들을 한 번에 쓰기 => 속도 더 빠름
    }
}