백준 - 14002 가장 긴 증가하는 부분 수열 4(Java)

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

14002번: 가장 긴 증가하는 부분 수열 4

 

동적 프로그래밍(DP) 및 역추적 문제입니다.

위 문제는 백준 11053문제와 거의 동일합니다.(https://ksb-dev.tistory.com/100에 11053번 문제에 대해 설명해 놨습니다.)

11053번 문제는 부분 배열중 가장 긴 길이의 크기만 출력하면 되지만,

14002번 문제는 길이 및 부분 배열을 이루는 요소들까지 출력해야 합니다.

 

가장 긴 부분 배열의 길이는 동적 프로그래밍으로 해결하고, 부분 배열의 요소들은 역추적으로 해결하면 됩니다.

가장 긴 부분의 길이를 구하는 동적 프로그래밍의 방법은 매우 간단합니다.

배열의 길이만큼 반복을 하고, 해당 위치에서 이전의 요소들만을 확인하면 됩니다.

예를 들어, DP[4]의 경우 자신 이전의 것들만 확인하면서 가장 큰 값을 지닌 DP[2]의 값인 2에 +1을 하면 됩니다.

 

역추적의 경우는, 별도의 배열을 사용해 값을 가져온 곳의 위치를 현재 위치에 저장합니다.

즉, 자기 자신의 부모를 저장합니다.

그림과 같이 {10, 20, 10, 30, 20, 50}이 있을 때 다음 그림과 같이 역추적 배열이 만들어 질 수 있습니다.

가장 긴 부분 배열을 지닌 6번 부터 시작하여, 자기 자신의 부모를 역추적하여 요소를 찾으면 됩니다.

private static void traceBack(int lo){
    // revArr는 역추적 배열
    if (revArr[lo] != lo) {
        traceBack(revArr[lo], bw);
        bw.write(arr[lo] + " "); // 부분 배열중 가장 작은 것 부터 출력됨됨
    }
    return;
}

 

코드를 보니 어디선가 본 적이 있지 않나요?

네, 맞습니다.

유니온 파인드(Union-find)에서 find를 할 때 사용되는 것과 매우 유사합니다.

find 역시 자기 자신의 부모를 찾아가기 때문입니다.

 

[구현 코드]

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int n;
    private static int[] arr, dp, revArr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz;

        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1];
        dp = new int[n + 1];
        revArr = new int[n + 1]; // 역추적

        stz = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i < n + 1; i++) {
            arr[i] = Integer.parseInt(stz.nextToken());
        }

        Arrays.fill(dp, -1);

        int maxPLen = 0; // 가장 긴 부분배열의 길이
        int lo = 0;
        for (int i = 1; i < n + 1; i++) {
            int len = lis(i);
            if (len > maxPLen) {
                maxPLen = len;
                lo = i;
            }
        }

        // 길이 출력
        bw.write(maxPLen+"\n");

        if(revArr[lo] == 0) {
            // 역추적 할 것이 없다면 자기 자신 출력
            bw.write(String.valueOf(arr[lo]));
        }else{
            // 역추적
            traceBack(lo, bw);

        }

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

    private static void traceBack(int lo, BufferedWriter bw) throws IOException {
        if (revArr[lo] != lo) {
            traceBack(revArr[lo], bw);
            bw.write(arr[lo] + " "); // 부분 배열중 가장 작은 것 부터 출력됨됨
       }
        return;
    }

    private static int lis(int i) {
        // 아직 탐색하지 않았다면
        if (dp[i] == -1) {
            dp[i] = 1; // 자기 자신

            // 자기 자신 위치 이전의 것을 봐서 작은 것을 찾음
            for (int j = i - 1; j > 0; j--) {
                if (arr[i] > arr[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        revArr[i] = j;
                    } else {
                        dp[i] = dp[i];
                    }
                }
            }
        }

        return dp[i];
    }
}