[백준] 11054 : 가장 긴 바이토닉 부분 수열 (JAVA)

https://www.acmicpc.net/problem/11054

 

🚩DP

백준 11053번 문제인 '가장 긴 증가하는 부분 수열'을 풀어본 경험이 있어서 쉽게 접근할 수 있었습니다.

11053번은 단순히 오른쪽 방향으로 증가하는 가장 긴 부분 수열을 구하는 문제였지만, 이번 문제는 증가 후 감소하는 가장 긴 부분 수열을 찾아야 했습니다.

 

부분 수열 문제는 보통 DP나 이분 탐색을 활용해서 해결하는 경우가 많기 때문에, 이번에도 DP로 접근했습니다.

 

🤔 증가 후 감소하는 부분 수열..?

한쪽 방향으로 증가하는 가장 긴 부분 수열 문제만 풀어서 그런가.. 증가 후 감소하는 부분 수열 구현이 바로 떠오르지 않았습니다.

곰곰이 고민한 끝에, 왼쪽에서 증가하는 부분 수열과 오른쪽에서 증가하는 부분 수열 각각 구한 후, 두 값을 더해 최댓값을 구하고 중복된 1만 빼면 되겠다는 아이디어가 떠올랐습니다💡

 

왼쪽에서 시작하는 부분 수열 int[] left, 오른쪽에서 시작하는 부분 수열 int[] right 이렇게 각각 생성한 뒤, 기본 DP 알고리즘을 활용해 각각 배열의 값을 채워 넣었습니다. 이후 left[i] + right[i] 최댓값을 구하고, 동일한 위치에서 중복 측정된 값을 조정하기 위해 최종적으로 -1을 해주었습니다.

 

---

 

아래는 DP로 접근한 코드입니다.

import java.io.*;
import java.util.*;

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];
        int[] left = new int[N];
        int[] right = new int[N];

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

        // left
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    left[i] = Math.max(left[j] + 1, left[i]);
                }
            }
        }

        // right
        for (int i = N - 2; i >= 0; i--) {
            for (int j = N - 1; j > i; j--) {
                if (arr[i] > arr[j]) {
                    right[i] = Math.max(right[j] + 1, right[i]);
                }
            }
        }

        int sum = 0;
        for (int i = 0; i < N; i++) {
            if (left[i] + right[i] > sum) {
                sum = left[i] + right[i];
            }
        }

        sum -= 1;
        bw.write(sum + "");
        bw.close();
    }
}