[백준] 11053번 가장 긴 증가하는 부분 수열 _ JAVA ( 주석 설명 )

풀이

1) dp[i] : ary[0]~ary[i-1] 까지 탐색을 하며 ary[i]보다 작은 값의 갯수를 저장한다.


2) 식을 세워보면
for(int i=N-1;i>=0;--i){
	if(ary[i]<ary[N)]{
    	
    }
}
일 때, dp[] 가 갱신된다.


3) 조건이 만족될 시
dp[N] = Math.max(dp[N], solve(i)+1);
을 통해 ary[N]보다 작은 원소의 개수를 찾는다.


4)
Top-down 방식에서는
solve(N-1)을 하면 dp[N-1]과 ary[N-1]보다 작은 값들의 dp[]가 구해지므로,
solve(0)~solve(N-1)까지 모두 실행해준다.


5)
Bottom-up 방식에서는
dp[i]<=dp[j] (i>j) 일 때의 조건도 포함시켜 => 제일 큰 값으로 유지해야 하므로
dp[0]~dp[N-1]까지 모두 구해주면 된다.

 

---

 

1번

→ Top-down 방식

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

public class Main {
    static int[] ary; //입력되는 수열의 값을 받는다.
    static int[] dp; //i번째 값보다 작은 값들을 저장하는 배열

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

        int N = Integer.parseInt(br.readLine());
        ary = new int[N];
        dp = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;++i){
            ary[i] = Integer.parseInt(st.nextToken());
        }
        //solve(N-1) 한 번만 하면, ary[N]을 기준으로 그보다 작은 값의 dp 만 계산될 것이다.
        //따라서, 0 ~ N-1 전부 실행하면서, dp[0] ~ dp[N-1]을 구해야 한다.
        for(int i=0;i<N;++i){
            solve(i);
        }



        int dp_max = dp[0];
        //dp[] 원소 중 가장 길이가 긴 부분수열의 값을 찾는다.
        for(int dp_value : dp){
            dp_max = Math.max(dp_max, dp_value);
        }

        System.out.println(dp_max);
    }

    //Top-down 방식
    private static int solve(int N) {
        if(dp[N] == 0) {
            dp[N] = 1; //기본적으로 부분 수열의 길이는 1을 가지고 있다.

            for (int i = N - 1; i >= 0; --i) {
                //ary[N] 보다 작은 수에 대한
                //1)가장 긴 부분 수열의 길이의 하나가 나온다.
                //2)i-- 될수록 1)의 ary[i] 보다 큰 값이 나타나, 작은 수가 더 많아져 dp[N]이 갱신될 수 있다.
                //  그러므로 1)의 값을 저장해, 다음 solve(i)+1 값과 비교한다.
                if (ary[i] < ary[N]) {
                    //+1 을 하는 이유 : 이전 부분수열에 ary[i]보다 큰 N번째 원소가 추가되었다.
                    //5, 10, 20, 30, 20, 50 이라면
                    //N == 3 일 때
                    //30보다 작은 값 solve(2)을 통해 20보다 작은 값의 개수를 찾고
                    //10에서는 10보다 작은 값, 5에서는 5보다 작은 값
                    //각각 +1 을 하면서 dp[N]을 찾는다.
                    dp[N] = Math.max(dp[N], solve(i) + 1);

                    //dp[N] = solve(i) + 1; 이 안되는 이유
                    //N == 5 일 때
                    //solve(4)+1; 보다 그 다음 i인
                    //solve(3)+1 이 더 크다.
                }
            }
        }

        return dp[N]; //dp[N] 값이 메모제이션이 되어 있으면 바로 리턴한다.
    }
}

 

---

 

2번

→ Bottom-up 방식

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

public class Main {
    static int[] ary; //입력되는 수열의 값을 받는다.
    static int[] dp; //i번째 값보다 작은 값들을 저장하는 배열

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

        int N = Integer.parseInt(br.readLine());
        ary = new int[N];
        dp = new int[N];

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

        solve2(N-1); //dp 최대 인덱스는 N-1이다.

        int dp_max = dp[0];
        //dp[] 원소 중 가장 길이가 긴 부분수열의 값을 찾는다.
        for(int dp_value : dp){
            dp_max = Math.max(dp_max, dp_value);
        }

        System.out.println(dp_max);
    }

    //Bottom-up 방식
    private static int solve2(int N){
        for(int i=0;i<=N;++i){
            //dp[i]의 초기값은 1이다.
            //기본적으로 자기 자신이 있으므로 부분 수열의 길이는 1이다.
            dp[i]=1;

            for(int j=0;j<i;++j){
                //본인보다 작은값일 경우와
                //dp값이 본인보다 클 경우 (제일 큰 값으로 유지해야 되므로)
                //dp를 갱신해준다.
                if(ary[i]>ary[j] && dp[i]<=dp[j])
                    dp[i] = dp[j]+1;
            }
        }

        return dp[N];
    }
}