[백준] 11054번: 가장 긴 바이토닉 수열 - Java, 자바

문제접근

이 문제는 어떤한 값 기분으로 왼쪽은 증가하는 수열 [LIS] 오른쪽으로는 감소하는 수열[LDS]이란걸 알 수 있다.
그렇다면 이 문제 같은경우는 어떻게 풀면될까.. 하고 생각해보면
어떠한 수열의 값 N을 기준으로 왼쪽으로는 LIS를 오른쪽으로는 LDS를 진행해준 후 두 개의 배열의 값을 합친 값 중
가장 큰 값을 출력하면 되지 않을까란 생각이 들 수 있다.
말 그대로 N을 기준으로 N - 1 부터 시작하여 0까지는 LIS를 통해 LIS_DP를 초기화하고,
N + 1 부터 시작하여 length - 1까지는 LDS를 통해 LDS_DP를 초기화하여 두 개의 배열의 합을 구하면 된다.
여기서 하나더, 이전에 LDS문제는 비교할 때 (number[N] < number[j]) 가 성립할 때 였는데 이때는 0 부터 시작하여 N까지 였기 때문에 N 기준 앞 쪽의 수가 더 컸어야 했지만, 여기서는 반대로 N부터 시작하여 Length - 1 까지 순회하기 때문에 N이 더 커야 한다는 것을 명심하자.
(number[N] > number[j])
여기서 조심해야 하는 것은 LIS,LDS 2번을 하게 되면 자기자신 N이 2번 들어가기 때문에 두 개의 합한 값에 -1을 반드시 해주어야한다.

전체코드

import java.awt.im.InputContext;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[] numbers;

    static Integer[] lis_dp;
    static Integer[] lds_dp;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        numbers = new int[N];

        lis_dp = new Integer[N];
        lds_dp = new Integer[N];

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

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

        for(int i = 0; i < N; i++) {
            recur_lis(i);
        }

        for(int i = N - 1; i >= 0; i--) {
            recur_lds(i);
        }

        int max = Integer.MIN_VALUE;

        for(int i = 0; i < N; i++) {

            max = Math.max(max, recur_lds(i) + recur_lis(i) - 1);
        }

        System.out.println(max);
    }


    static int recur_lis(int N) {

        if(lis_dp[N] == null) {
            lis_dp[N] = 1;

            for(int i = N - 1; i >= 0; i--) {

                if (numbers[N] > numbers[i]) {
                    lis_dp[N] = Math.max(lis_dp[N], recur_lis(i) + 1);
                }
            }
        }


        return lis_dp[N];
    }


    static int recur_lds(int N) {

        if(lds_dp[N] == null) {
            lds_dp[N] = 1;

            for(int i = N + 1; i < lds_dp.length; i++) {
                if(numbers[N] > numbers[i])  {
                    lds_dp[N] = Math.max(lds_dp[N], recur_lds(i) + 1);
                }
            }
        }

        return lds_dp[N];
    }
}

정리

LIS 와 LDS를 알고 조합 할 수 있었다면 쉽게 해결할 수 있었을 것이다. LIS, LDS를 하되, 모두 N에서 시작하기 때문에 N의 값(1)이 중복되기 때문에 답에서 -1을 해주는 것이 중요했다.