[백준] 11053. 가장 긴 증가하는 부분 수열(LIS) - JAVA

문제

---

풀이

 

처음에는 DFS의 재귀를 이용해서 약 2시간동안 풀어보았다.

 

import java.io.*;

import java.util.*;

 

public class Main{

    static StringBuilder sb = new StringBuilder();

    static int N,Max,cur;

    static int[] arr;

 

    static void dfs(int cur,int depth,int count){

        if(depth == N){

            Max = Math.max(count, Max);

            return;

        }

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

            if(arr[i]>cur){

                dfs(arr[i],depth+1,count+1);

            }

            else{

                dfs(cur,depth+1,count);

            }

        }

    }

   

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        N = Integer.parseInt(st.nextToken());

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

        arr = new int[N];

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

            arr[i] = Integer.parseInt(st.nextToken());

        }

        Max=1;

        dfs(0,0,0);

        System.out.print(Max);

    }

}

 

하지만,

시간 초과가 되어 DFS가 아니라는 것을 느꼈다.

 

DFS로 한 경우 재귀하여 모든 부분을 다시 탐색하기 때문에 O(2^n) 으로

정말 최악의 시간 복잡도가 나온다.

 

따라서 이 문제의 알고리즘은 DP로 다가가야 한다.

DP로 다가가면 O(n^2)으로 DFS와 달리 훨씬 빠르다.

 

arr[0]~arr[N] 중 가장 긴 수열을 찾아내기 위해서는

우선, DP의 모든 배열의 수를 1을 넣어준다.(기본값이다)

그 후 DP의 한칸씩 넘어가면서 DP와 arr의 같은 인덱스 i에서
arr[i] 보다 작은것들중에 가장큰 값의 DP를 찾고 +1을 하여 DP[i] 를 갱신한다.

점화식은

DP[i] = Math.max(DP[i]),DP[k]+1) 를 활용하면 된다.  

 

---

코드

import java.io.*;

 

import java.util.*;

 

public class Main{

    static int N;

    static int[] DP,arr;

 

    static void LIS(){

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

            for(int k=0; k<i; k++){

                if(arr[i]>arr[k]){

                    DP[i] = Math.max(DP[i], DP[k]+1);

                }

            }

        }

    }

 

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        N = Integer.parseInt(st.nextToken());

        DP = new int[N];

        arr = new int[N];

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

        Arrays.fill(DP,1);

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

            arr[i] = Integer.parseInt(st.nextToken());

        }

        LIS();

        int result = DP[0];

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

            result = Math.max(result,DP[i]);

        }

        System.out.print(result);

    }

}