백준_가장 긴 증가하는 부분 수열(11053) In Java

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

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

이런 문제를 최장 증가 부분 수열(LIS)라고 한다.

증가 부분 수열에 대해서는 여기를 클릭해서 보면 된다.

 

Top-Down 코드&풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] ar;
    static Integer[] dp;

    static int LIS(int N){
        if(dp[N]==null){
            dp[N]=1;
            for (int i = N-1; i >=0 ; i--) {
                if(ar[i]<ar[N]){
                    dp[N] = Math.max(dp[N], LIS(i) + 1);
                }
            }
        }
        return dp[N];
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int i = 0; i < N; i++) {
            LIS(i);
        }
        int max = dp[0];
        for (int i = 0; i < N; i++) {
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}

N을 인자로 전달받는 LIS 함수를 N번째 값에 값이 입력이 되있지않다면 1로 초기화(길이는 항상 1이상이기 때문에)한 후 N-1부터 0부터 N이하까지 값들을 탐색하여 N번째 값보다 작은 값을 찾는다. 모든 재귀함수가 끝났을때에는

dp[] 배열을 돌면서 최대값을 뽑아 최대값을 출력하면된다.

 

Bottom-Up 코드&설명

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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[] ar = new int[N];
        int[] dp = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            ar[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 0; i < N; i++) {
            dp[i]=1;

            for (int j = 0; j < i; j++) {
                if(ar[j]<ar[i]&&dp[i]<dp[j]+1){
                    dp[i]=dp[j]+1;
                }
            }
        }
        int max=-1;
        for (int i = 0; i < N; i++) {
            max=Math.max(dp[i],max);
        }
        System.out.println(max);
    }
}

 

이중 반복문을 통해 0부터 N-1까지 다 돌면서 각 원소들보다 큰값을 세는 방법이다.

 

시간복잡도는 O(NLogN)이 된다.