[JAVA] # 11053 가장 긴 증가하는 부분 수열(LIS)

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

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

import java.util.Scanner;

public class Main {

    static int N;
    static int[] nums;
    static int[] dp;

    public static void func() {
        for(int i = 0; i < N; i++) {
            dp[i] = 1;
            for(int j = 0; j < i; j++) {
                if(nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        nums = new int[N + 1];
        dp = new int[N + 1];
        for(int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
        }
        func();
        int max = 0;
        for(int i = 0; i < N; i++) {
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}

 

가장 증가하는 부분 수열(LIS, Longest Increasing Subsequence)

 

어떻게 풀어야 하는지 정말 막막했는데 막상 풀고나서 보니까 정말로 별거 아니었던 알고리즘이다..

 

dp[] 배열은 현재 인덱스에서 가능한 최대 증가 부분수열의 길이를 담는다.

 

예제 1 3 5 2 3 4 를 생각해보자

 

idx = 0

dp[idx] 의 최솟값은 1이다.

왜냐하면 부분수열의 길이가 최소 1(본인)이기 때문이다.

 for(int i = 0; i < N; i++) {
            dp[i] = 1;

idx = 1

idx = 1이다.

int j = 0; j < idx; j++ 반복문으로 idx가 증가할때마다 앞에 있는 dp 배열을 전부 탐색해볼 것이다.

 

nums[j] < nums[idx] 인 경우에만 체크한다.

증가하는 부분수열이기 때문에 수열에 마지막에 제일 큰 값이 와야하기 때문.

 

이 경우에 Math.max(dp[idx], dp[j] + 1)으로 최댓값을 저장한다.

(dp[j] 의 길이에 자신이 추가됨으로써 dp[j] + 1이 최댓값)

    public static void func() {
        for(int i = 0; i < N; i++) {
            dp[i] = 1;
            for(int j = 0; j < i; j++) {
                if(nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
    }

 

이렇게 완성된 것이 LIS의 길이를 찾아내는 알고리즘이다 (O(N^2))

 

 

 

이렇게 보면 별거 아닌데 왜이렇게 어려웠는지 모르겠다.

 

유사한 문제로 #11722 가장 긴 감소하는 부분수열 문제가 있는데,

(https://www.acmicpc.net/problem/11722)

 

이건 그냥 수열을 뒤집어놓고 증가 부분수열 알고리즘을 적용하면 그대로 풀린다 :D