[Java] 백준 BOJ / 11054번: 가장 긴 바이토닉 부분 수열

가장 긴 바이토닉 부분 수열

문제

---

문제 설명

가장 긴 바이토닉 부분 수열을 구하는 문제이다.
바이토닉 부분 수열이란 연속적으로 계속 증가하거나, 계속 감소하거나, 증가하다가 감소하는 수열을 말한다.

문제에서 예를 든것 처럼 {10, 20, 30, 40, 50} , {10, 20, 30, 25, 20} 등이 있다.

이 문제를 풀 때 처음에 DP 배열을 하나로 두고 2차원으로 풀어야 하나 했었는데 생각해보니 왼쪽부터 시작하는 DP 배열 하나, 오른쪽부터 시작하는 DP 배열을 하나 해서 총 두개의 DP배열을 사용해서 구할 수 있다는 생각을 하게 되었다.

이렇게 구하는 DP 배열은 11053번: 가장 긴 증가하는 부분 수열 문제에서도 풀 수 있다.

이 문제에서와 마찬가지로 그냥 가장 긴 증가하는 부분 수열을 두개 구하면 된다.

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

위 코드와 같이 이중 for문을 돌리면서 현재 위치를 기준으로 이전 숫자들을 탐색하면서 만약 탐색중인 값인 arr[j]가 기준 값인 arr[i] 보다 작고 해당 i 값에서의 dp값이 현재 j 값에서 1을 더한것보다 작다면 dp[i] 값을 초기화 해주는 방식으로 했다.

이와 같은 방식으로 감소하는 수열은 배열의 크기인 n부터 거꾸로 탐색하면 되는데 해당 코드는 아래와 같다.

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

이렇게 나온 dpLeft 배열과 dpRight 배열을 비교하면 되는데 비교해야 하는 값은 위에서 말한 것처럼 총 3개의 값이다.

• 계속 증가하는 값 중 최대값 : Math.max(dpLeft[i])
• 계속 감소하는 값 중 최대값 : Math.max(dpRight[i])
• 증가하다가 감소하는 값 중 최대값 : Math.max(dpLeft[i] + dpRight[i])

이렇게 세가지의 값 중 최대를 구하면 끝나는 문제이고 최종 코드는 아래와 같다.

---

코드

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

public class Main_11054 {
    static int n;
    static int[] arr;
    static int[] dpLeft;
    static int[] dpRight;

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

        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1];
        dpLeft = new int[n + 1];
        dpRight = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

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

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

        int result = 0;

        for (int i = 0; i <= n; i++) {
            int max = Math.max((dpLeft[i] + dpRight[i] - 1), Math.max(dpLeft[i], dpRight[i]));
            result = Math.max(max, result);
        }

        System.out.println(result);
    }
}