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

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

해결 방법

• 사용한 알고리즘: DP
• 접근 방법:
  • 테이블 정의: d[i]: 첫 시작 원소부터 i번째 원소까지 고려했을 때, 가장 긴 증가하는 수열의 길이
  • 점화식:
    • i번째 원소를 포함하지 않을 경우: d[i] = d[i-1]
    • i번째 원소를 포함하는 경우(if 조건을 만족할 경우): for j < i => if(aj < ai && d[i] < d[j]+1) d[i] = d[j]+1
      • i번째 원소를 포함할 경우, i보다 작은 j에 대해 가장 긴 증가하는 수열의 길이 + 1을 하여 현재 i번째 가장 긴 증가하는 수열의 길이(d[i])와 비교하여 최대값으로 업데이트 한다.
    • 추가적으로 길이뿐만 아니라, 가장 긴 증가하는 부분 수열을 출력해야 한다. 이를 위해 역추적 배열을 썼다.
      • for j < i => if(aj < ai && d[i] < d[j]+1) d[i] = d[j]+1 이 과정에서 if문에 걸려 업데이트 된다면 pre[i] 값을 j로 설정해준다. 이를 통해 i이전에 j가 온다는 것을 기록해두는 것.
      • 이후, 가장 긴 증가하는 부분 수열의 길이(d 값)를 가진 지점을 마지막 인덱스(lastIdx)로 설정하고 역추적하여 부분수열을 찾는다.
      • 마지막으로 정렬을 하여 가장 긴 증가하는 부분 수열을 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Solution_14002_MW {

    static int n;
    static int[] a;
    static int[] pre;
    static int[] d;
    static List<Integer> subSequence = new ArrayList<>();
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        a = new int[n];
        String[] s = br.readLine().split(" ");
        for(int i=0; i<n; i++) {
            a[i] = Integer.parseInt(s[i]);
        }
        pre = new int[n];
        Arrays.fill(pre, -1);
        d = new int[n];

        for(int i=0; i<n; i++) {
            d[i] = 1;
            for(int j=0; j<i; j++) {
                if(a[i] > a[j] && d[i] < d[j]+1) {
                    pre[i] = j;
                    d[i] = d[j]+1;
                }
            }
        }

        int lastIdx = n-1;
        for(int i=n-1; i>=0; i--) {
            if(pre[i] != -1 && d[i] > d[lastIdx]) {
                lastIdx = i;
            }
        }

        System.out.println(d[lastIdx]);
        sub_sequence(lastIdx);

        Collections.sort(subSequence);

        for (Integer num : subSequence) {
            System.out.print(num + " ");
        }
    }

    public static void sub_sequence(int n) {

        if(n == -1) return;

        subSequence.add(a[n]);
        sub_sequence(pre[n]);
    }
}

문제 리뷰

• 간만에 LIS문제 복습했습니다. 다시 풀어도 DP는 생각하기 어렵습니다..
• 예전에 다익스트라 문제를 풀면서 경로 출력하는 문제를 풀어봐서, 역추적 배열은 쉽게 생각할 수 있었습니다.