[백준] 11054 가장 긴 바이토닉 부분 수열 - Dynamic Programming / Java

• 문제 링크

11054번: 가장 긴 바이토닉 부분 수열

 

• 풀이 과정

바이토닉 수열이란 특정 값을 기준으로 왼쪽 부분은 오름차순, 오른쪽 부분은 내림차순인 수열을 말한다.

 

따라서 왼쪽에서 오른쪽으로 오름차순인 부분 수열의 길이를 구하여 dpIn 배열에 저장하고,

오른쪽에서 왼쪽으로 오름차순인 부분수열, 즉 내림차순 부분 수열의 길이를 구하여 dpDe 배열에 저장한다.

 

이 후 각각 기준이 되는 원소의 두 부분수열의 길이 값을 더하여

오름차순과 내림차순이 합쳐진 바이토닉 부분수열의 길이를 구한다.

이때 기준이 되는 원소 1개가 중복되므로 구해진 최대값에 -1 을 수행하여 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

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

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        int[] dpIn = new int[n];
        for (int i = 0; i < n; i++) {
            dpIn[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && dpIn[i] < dpIn[j] + 1)
                    dpIn[i] = dpIn[j] + 1;
            }
        }

        int[] dpDe = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            dpDe[i] = 1;
            for (int j = n - 1; j > i; j--) {
                if (arr[j] < arr[i] && dpDe[i] < dpDe[j] + 1)
                    dpDe[i] = dpDe[j] + 1;
            }
        }

        int max = 0;
        for (int i = 0; i < n; i++)
            max = Math.max(max, dpIn[i] + dpDe[i]);

        bw.write(max - 1 + "\n");
        bw.flush();
    }

}