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

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

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

public class Main {
    int[] dp;
    int[] num;
    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        dp = new int[n];
        num = new int[n];
        for(int i=0; i<n; i++){
            num[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 0; i<n; i++){
            dp[i] = 1;
            for(int j = 0; j<i; j++){
                if(num[i]>num[j]&&dp[i]<dp[j]+1){
                    dp[i] = dp[j]+1;
                }
            }
        }

        int max = 0;
        for(int i=0; i<n; i++){
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
//    public int lis(int n){
//        if(dp[n]==0){
//            dp[n] = 1;
//            for(int i=n-1; i>=0; i--){
//                if(num[i]<num[n]){
//                    dp[n] = Math.max(dp[n], lis(i)+1);
//                }
//            }
//        }
//        return dp[n];
//    }

    public static void main(String args[]) throws IOException {
        new Main().solution();
    }
}

고민하다가 검색을 통해 풀이를 참고했다(https://st-lab.tistory.com/137)

주석처리 된 부분은 top-down / 풀이는 bottom-up 방식이다.

 

top-down

dp[n] = 1 로 초기화 (최소 길이1)

dp 에는 주어진 수열의 각 인덱스별 부분 수열 길이를 담는다.

dp[0] = 1 (10)

dp[1] = 2 (10,20)

dp[2] = 1 (10)

주어진 정수 n부터 시작해 n-1 부터 0까지 차례대로 크기를 비교한다.

dp[n] 에는 dp[n]과 재귀함수를 통한 결과를 비교해 큰 값을 저장한다.

 

bottom-up

dp[n] = 1 로 초기화 (최소 길이1)

dp 에는 주어진 수열의 각 인덱스별 부분 수열 길이를 담는다.

dp[0] = 1 (10)

dp[1] = 2 (10,20)

dp[2] = 1 (10)

주어진 정수 n까지 차례대로 수열들을 비교한다.

이중 for문을 통해 값을 비교하고

현재 인덱스인 i보다 값이 작고, dp[i]보다 dp[j]+1한 값이 클 경우 (중복제거)

dp[j]+1을 dp[i]에 저장한다.