[백준 JAVA] 11053번: 가장 긴 증가하는 부분 수열

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

 

LIS(Longest Increasing Subsequence) 의 기본형 문제

 

LIS란 주어진 수열에서 몇 개의 원소를 제거하여 원래 순서를 유지하면서 만들 수 있는 부분 수열 중 오름차순으로 가장 긴 수열을 말한다.

 

또한 DP 의 기본 문제라고도 할 수 있다.

 

dp[i] = A[i]로 끝나는 LIS 길이로 두고 j < i 이면서 A[j] < A[i]이면 dp[i] = max(dp[i], dp[j] + 1) 를 구하면 풀 수 있다.

 

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

public class Main {
    public static int N, ans = 0;
    public static int[] arr, dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        dp = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 0; i < N; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            ans = Math.max(ans, dp[i]);
        }

        System.out.println(ans);
    }
}

 

예전에도 이렇게 풀었었는데 이 방법은 시간복잡도가 O(N^2) 이지만 O(N log N) 으로도 풀 수 있는 방법이 있다고해서 찾아봤다.

 

이분탐색을 이용하는 방법으로 

 

tails[len] = 길이가 len인 증가 부분수열이 가질 수 있는 최소의 마지막 값

 

각 A[i]에 대해 tails에서 lower_bound(>=) 위치에 A[i]를 넣어 갱신

 

tails가 차오른 길이가 곧 LIS 길이(Strictly Increasing이므로 >=로 lower_bound)

 

이런식으로 푸는 방법이다.

 

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

public class Main {
    public static int N, len = 0;
    public static int[] arr, tails;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        tails = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int x : arr){
            int pos = lowerBound(x);
            tails[pos] = x;
            if(pos == len) len++;
        }

        System.out.println(len);
    }
    public static int lowerBound(int key) {
        int l = 0, r = len;
        while (l < r){
            int m = (l + r) >>> 1;
            if(tails[m] >= key) r = m;
            else l = m + 1;
        }
        return l;
    }
}

 

이 코드가 살짝 더 빠른걸 확인할 수 있었다.