💔가장 긴 증가하는 부분 수열 4

 

 

•  

1. 문제 설명

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

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

www.acmicpc.net

수열이 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 구하고, 해당 조건을 만족하는 부분 수열 중 하나를 출력하라.

→ 원래 최장 증가 부분 수열의 길이만 구하던 문제에서 이제 그 구성요소를 구하는 문제로 바뀌었다.

2. 푸는 원리

처음에 문제 푸는 데 정말 헤맸는데, 그 이유는 해당 문제도 다른 LIS처럼 이분탐색을 써서 풀려고 했기 때문이다. 하지만 이분탐색의 경우 큰 문제가 있는데, 바로 LIS의 구성요소를 구하기 힘들다는 점이다. 왜 그런지 한번 보자. 먼저 값을 구하기 위해 조작하는 배열을 A, 수열 전체를 담는 배열을 T라고 하자. Dp 풀이법에서는 A의 index i는 T[i]를 뜻하고, A[i]는 T[i]를 끝 값으로 가지는 LIS의 크기이다. 이분 탐색 풀이법에서는 A의 인덱스 i는 LIS의 길이를 뜻하고 T[i]는 LIS가 i라는 길이일 때 맨 끝 값으로 가질 수 있는 원소의 최소값이다. 따라서 전자인 DP 풀이법은 한번 T[i]의 값을 구하면 해당 값이 변동되지 않는다. A[i]가 맨 끝 값인 LIS는 수열 전체가 주어진 순간부터 이미 정해져 있기 때문이다. 반면 이분탐색에서의 T[i]는 갱신될 수 있다. 왜냐하면 길이가 3인 LIS값이 기존엔 5인 경우, 전체 수열의 원소를 하나하나 읽어갈수록 이보다 더 작은 3이 나올 수도 있기 때문이다. 이렇게 값이 계속 바뀐다면, 전체 배열을 구하고 LIS를 구한 뒤에 다시 복기 해가며, 최장 길이 부분 수열의 멤버를 구한다는 것은 쉽지 않다. 차라리 고정 불변의 A[i]를 가진 DP 풀이법을 쓰는 것이 LIS의 멤버를 구하기엔 더욱 용이하다.

따라서 위의 이유 때문에 DP 풀이법을 이용한다. DP는 주어진 전체 수열의 원소를 첫 값부터 하나하나 구해나가며, 그 상황에서의 부분 증가 수열의 길이를 구한다. → stack up이 이루어진다는 것이다. (하나 하나씩 갱신되어가며 쌓아나간다.) 위의 문제는 LIS의 구성요소도 같이 구하라고 했으므로, DP로 원소 하나하나씩 구해가면서, 부분 증가 수열의 길이가 커질 때마다, 추가되는 원소를 다른 곳에다가 저장해둔다. 나는 LIS DP 풀이법과 별개로 StringBuilder ArrayList를 가지고 있었다. 그리고 만약 부분증가수열의 길이가 길어질 때, 현재 조회 중인 인덱스가 i이면 T[i]를 끝 값으로 가지는 LIS를 ArrayList.get(i)번에 저장한다.

3. 코드 분석

Copy

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

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 [] arr = new int [N+1];

        // 각 인덱스가 해당 arr[i]를 마지막으로 하는 최장 연속 수열의 값들이 저장되어 있음.
        ArrayList<StringBuilder> LIS = new ArrayList<>();

        // index -> arr의 index를 가리킴
        // 값 -> 배열 속 해당 인덱스의 값을 끝으로 하는 최장 연속 수열의 길이
        int [] dp = new int [N+1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.fill(dp, 1);
        dp[0] = 0;
        LIS.add(new StringBuilder());
        LIS.add(new StringBuilder().append(arr[1]).append(" "));

        for (int i = 2; i <= N; i++) {

            int max = 1;
            int maxIndex = 0;
            for (int j = 1; j <= i; j++) {
                if(arr[j] < arr[i]){
                    // 지금까지 알아본 최장 길이보다 더 긴 수열이 가능하다.
                    if(max < dp[j] + 1){

                        // 길이 갱신, 맨 끝값의 index 기록
                        max = dp[j] + 1;
                        maxIndex = j;
                    }
                }
            }
            dp[i] = max;
            // arr[i]를 맨 끝에 넣을 수 있는 최장 연속 수열 +  arr[i]의 값
            LIS.add(new StringBuilder().append(LIS.get(maxIndex)).append(arr[i]).append(" "));


        }

        int maxDP = 0;
        int maxDPIndex = 0;
        for (int i = 0; i < dp.length; i++) {
            if(dp[i] > maxDP){
                maxDPIndex = i;
                maxDP = dp[i];
            }
        }

        System.out.printf("%d \n%s", maxDP, LIS.get(maxDPIndex));
    }
}