[실버2, DP] 백준 11053 - 가장 긴 증가하는 부분 수열 (자바)

Think

1. LIS인 이 문제를 보고 고민해보았으나, 풀이 접근 방법이 떠오르지 않음 (이걸 dp로 어떻게 풀지..? 라는 생각)

2. https://st-lab.tistory.com/137 를 참고하여 풀이 방법을 공부함

3. 현재 수열 기준으로 이전 값들을 탐색하며 이전 값이 더 작다면 해당 인덱스의 dp 값 + 1과 현재 dp값을 비교하여 최대값을 저장해준다

4. 해당 풀이법은 시간복잡도가 N^2라고 하며, 이분탐색을 활용하면 NlogN까지 가능하다고 함

 

 

 

 

제출 코드 (Top-down)

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

public class Main {
    static int n, t, z , o;
    static int sequence[];
    static Integer dp[];

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

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

        progress();
    }

    private static void progress() {

        for (int i = 0; i < n; i++) {
            recursion(i);
        }


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

    }

    private static int recursion(int number) {

        if(dp[number] == null){
            dp[number] = 1;

            for (int i = number - 1; i >= 0; i--) {
                if(sequence[i] < sequence[number]){
                    dp[number] = Math.max(dp[number], recursion(i) + 1);
                }
            }
        }

        return dp[number];
    }

    private static void init() throws IOException {
        n = Integer.parseInt(br.readLine());

        sequence = new int[n];
        dp = new Integer[n];

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

        int i = 0;
        while(st.hasMoreTokens()){
            sequence[i++] = Integer.parseInt(st.nextToken());
        }
    }

}

 

 

제출 코드2 (Bottom-up)

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

public class test {
    static int n;
    static int sequence[];
    static Integer dp[];

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

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

        progress();
    }

    private static void progress() {

        for (int i = 0; i < n; i++) {
            if(dp[i] == null){
                dp[i] = 1;

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

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

    }

    private static void init() throws IOException {
        n = Integer.parseInt(br.readLine());

        sequence = new int[n];
        dp = new Integer[n];

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

        int i = 0;
        while(st.hasMoreTokens()){
            sequence[i++] = Integer.parseInt(st.nextToken());
        }
    }

}