문제 출처

단계별로 풀어보기 > 동적 계획법 1 > 가장 긴 바이토닉 부분 수열
https://www.acmicpc.net/problem/11054

문제 설명

수열 S가 어떤 수 Sk를 기준으로 S1<S2<...Sk-1<Sk>...SN-1>SN을 만족하면 바이토닉 수열이다.
수열 A가 주어질 때, 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하라.

접근 방법

기본적으로 LIS(주어진 수열에서 오름차순으로 정렬된 가장 긴 부분의 수열의 길이를 구하는 알고리즘), LDS(주어진 수열에서 내림차순으로 정렬된 가장 긴 부분 수열의 길이를 구하는 알고리즘)을 이용하는 문제이다.
가장 긴 바이토닉 수열은 LIS + LDS를 이용하여 구할 수 있다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 가장_긴_바이토닉_부분_수열 {

    public static int[] r_dp;
    public static int[] l_dp;
    public static int[] array;
    public static int N;

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

        r_dp = new int[N];
        l_dp = new int[N];
        array = new int[N];

        Arrays.fill(r_dp, 1);
        Arrays.fill(l_dp, 1);

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

        LIS();
        LDS();

        int max = 0;
        for (int i = 0; i < N; i++) {
            max = Math.max(max, r_dp[i] + l_dp[i] - 1);
        }

        System.out.println(max);
        br.close();
    }

    public static void LIS() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (array[j] < array[i]) {
                    r_dp[i] = Math.max(r_dp[i], r_dp[j] + 1);
                }
            }
        }
    }

    public static void LDS() {
        for (int i = N - 1; i >= 0; i--) {
            for (int j = N - 1; j > i; j--) {
                if (array[j] < array[i]) {
                    l_dp[i] = Math.max(l_dp[i], l_dp[j] + 1);
                }
            }
        }
    }
}

Review

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class 가장_긴_바이토닉_부분_수열_review {

    public static int array[];
    public static int l_dp[];
    public static int r_dp[];
    public static int N;

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

        array = new int[N];
        l_dp = new int[N];
        r_dp = new int[N];

        Arrays.fill(l_dp, 1);
        Arrays.fill(r_dp, 1);

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

        for(int i = 0; i<N; i++){
            array[i] = Integer.parseInt(st.nextToken());
        }

        LIS();
        LDS();

        int max = 0;

        for(int i = 0; i<N; i++){
            max = Math.max(l_dp[i] + r_dp[i] - 1, max);
        }


        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
        br.close();

    }

    public static void LIS(){
        for(int i = 0; i<N; i++){
            for(int j = 0; j<i; j++){
                if(array[j] < array[i]){
                    r_dp[i] = Math.max(r_dp[i], r_dp[j] + 1);
                }
            }
        }
    }

    public static void LDS(){
        for(int i = N-1; i>=0; i--){
            for(int j = N-1; i<j; j--){
                if(array[j] < array[i]){
                    l_dp[i] = Math.max(l_dp[i], l_dp[j] + 1);
                }
            }
        }
    }

}

알게된 점

LIS, LDS, 바이토닉 수열에 대해서 알게 되었다.
LIS 문제를 풀 때, LIS, LDS의 구현 방법과 구현 코드를 더 자세히 다뤄봐야겠다.

Review
LDS의 조건이 헷깔렸었다.
오른쪽에서 왼쪽으로 갈 때, 감소하는 수열의 길이를 체크하면 되는 것인데, 자꾸 정방향으로 생각해서 array[j] < array[i]의 조건을 array[j] > array[i]로 착각했었다.

문제푼 흔적