[백준] 11054번 가장 긴 바이토닉 부분 수열 _ JAVA ( 주석 설명 )

풀이

1)

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

2 - dp2[i] : ary[i]~ary[N] 까지 탐색을 하며 ary[i]보다 작은 값의 갯수를 저장한다.

-> 증감을 파악하기 위해서



2)

'가장 긴 증가하는 부분 수열' 문제와 같이 처음 dp1[N], dp2[N] == 0 (빈 값) 일 때, 자기 자신도 갯수에 포함해야 하므로 1로 초기화 한다.


3)

dp1[N]을 구하는 함수에서는 1)-1 식을 코드로

dp2[N]을 구하는 함수에서는 2)-2 식을 코드로 작성을 한다.



ex> dp1

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


4)

dp1[], dp2[] 배열에 각 인덱스에 있는 원소를 기준으로 증감을 담았기 때문에,
가장 긴 바이토닉 부분 수열은 dp1[], dp2[] 의 각 인덱스를 더한 값 중 가장 큰 값이다.

 

---

 

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[] dp1; //증가하는 부분수열을 담을 공간이다.
    static int[] dp2; //감소하는 부분수열을 담을 공간이다.

    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];
        dp1 = new int[N];
        dp2 = new int[N];


        //수열 A를 입력받는다.
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;++i){
            ary[i] = Integer.parseInt(st.nextToken());
        }

        //dp1[] 구하기
        for(int i=0;i<N;++i) {
            increase_length(i);
        }

        //dp2[] 구하기
        for(int i=0;i<N;++i) {
            decrease_length(i);
        }


        //증가 추세와 감소 추세를 담은 dp1, dp2 배열의 합이 바이토닉 부분 수열이다.
        //이 중 가장 긴 바이토닉 부분 수열을 찾는다.
        //본인 자신이 2번 카운팅 되기 때문에 -1을 해준다.
        int in_de_length = 0;
        for(int i=0;i<N;++i){
            in_de_length = Math.max(in_de_length, dp1[i]+dp2[i]-1);
        }

        System.out.println(in_de_length);
    }

    //N 이전의 증가 배열의 부분수열 중 가장 큰 길이의 값
    private static int increase_length(int N) {
        if(dp1[N]==0) {
            dp1[N] = 1;
            //본인보다 작은 인덱스에서 작은 값의 갯수를 찾는다. => 0~N까지 증가 추세
            for(int i=0;i<N;++i){
                if(ary[N] > ary[i]) {
                    dp1[N] = Math.max(dp1[N], increase_length(i) + 1);
                }
            }
        }
        return dp1[N];
    }

    //N 이후의 감소 배열의 부분수열 중 가장 큰 길이의 값
    private static int decrease_length(int N) {
        if(dp2[N]==0) {
            dp2[N] = 1;
            //본인보다 큰 인덱스에서 작은 값의 갯수를 찾는다. => N~ary.length 까지 감소 추세
            for(int i=N;i< ary.length;++i) {
                if (ary[N] > ary[i]) {
                    dp2[N] = Math.max(dp2[N], decrease_length(i) + 1);
                }
            }
        }
        return dp2[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[] dp1; //증가하는 부분수열을 담을 공간이다.
    static int[] dp2; //감소하는 부분수열을 담을 공간이다.

    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];
        dp1 = new int[N];
        dp2 = new int[N];


        //수열 A를 입력받는다.
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;++i){
            ary[i] = Integer.parseInt(st.nextToken());
        }


        increase_length(N-1);
        decrease_length(N-1);


        //증가 추세와 감소 추세를 담은 dp1, dp2 배열의 합이 바이토닉 부분 수열이다.
        //이 중 가장 긴 바이토닉 부분 수열을 찾는다.
        //본인 자신이 2번 카운팅 되기 때문에 -1을 해준다.
        int in_de_length = 0;
        for(int i=0;i<N;++i){
            in_de_length = Math.max(in_de_length, dp1[i]+dp2[i]-1);
        }

        System.out.println(in_de_length);
    }

    //N 이전의 증가 배열의 부분수열 중 가장 큰 길이의 값
    private static int increase_length(int N) {
        //j<i
        //dp 계산을 할 때, 그 직전 값을 계산해야 하므로, 0부터 시작을 해야한다.
        for(int i=0;i<=N;++i){
            //dp1[i]의 초기값은 1이다.
            //기본적으로 자기 자신이 있으므로 부분 수열의 길이는 1이다.
            dp1[i] = 1;
            for(int j=0;j<i;++j) {
                //본인보다 작은값일 경우와
                //dp값이 본인보다 크거나 같을 경우 (제일 큰 값으로 유지해야 되므로)
                //dp를 갱신해준다.
                if (ary[j] < ary[i] && dp1[i] <= dp1[j]){
                    dp1[i] = dp1[j] + 1;
                }
            }
        }
        return dp1[N];
    }

    //N 이후의 감소 배열의 부분수열 중 가장 큰 길이의 값
    private static int decrease_length(int N) {
        //j>i
        //dp 계산을 할 때, i를 기준으로 뒤에서 계산을 해야하므로 N부터 계산을 해야한다.
        for(int i=N;i>=0;--i){
            //dp1[i]의 초기값은 1이다.
            //기본적으로 자기 자신이 있으므로 부분 수열의 길이는 1이다.
            dp2[i] = 1;
            for(int j= ary.length-1;j>i;--j){
                //i를 기준으로 그 뒤의 값(j>i)을 계산해야 하므로,
                //dp값이 본인보다 크거나 같을 경우 (제일 큰 값으로 유지해야 되므로)
                //dp2를 갱신해준다.
                if(ary[j] < ary[i] && dp2[i] <= dp2[j]){
                    dp2[i] = dp2[j] + 1;
                }
            }
        }
        return dp2[N];
    }
}