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

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

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

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

이번에 알게 된 것인데, 가장 긴 증가하는 부분 수열을 구하는 알고리즘을 부르는 명칭이 존재했다.

이는 LIS 알고리즘으로, Longes Increasing Subsequence 의 줄임말이다.

 

이번 바이토닉 부분 수열을 구할 때에 이 LIS 알고리즘을 잘 적용하여야 한다.

 

 

가장 긴 바이토닉 부분 수열은 증가하다가 감소하는 부분 수열의 길이가 가장 긴 것을 구해야 한다.

 

이를 다시 말하면,

1. 증가하는 부분 수열의 길이 값도 최대로

2. 감소하는 부분 수열의 길이 값도 최대로 하여야 한다.

 

즉, 증가하는 부분 수열의 dp 배열 값과 감소하는 부분 수열의 dp 배열 값을 서로 더하여 최댓값을 찾는다면 1, 2를 모두 충족할 것이다.

 

참고로 dp 배열은 해당 원소까지 가장 긴 증가 or 감소하는 부분 수열의 개수를 나타낸다.

 

 

먼저 증가하는 부분 수열의 길이를 구해보자.

 

다음으로 감소하는 부분 수열의 길이를 구해보자.

이는 뒤에서부터 증가하는 부분 수열의 길이를 구하는 것과 동일하다.

 

이 두 dp배열의 합의 최댓값은 8로,

dpLR에서는 1, 2, 4, 5가 선택되고 dpRL에서는 5, 2, 1가 선택되는데 5가 중복되므로 1을 빼준다.

 

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int arr[] = new int[N + 1];
		for (int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		// 왼쪽에서 오른쪽으로 LIS 구하기
		int[] dpLR = new int[N + 1];
		for (int i = 1; i <= N; i++) {
			dpLR[i] = 1;
			for (int j = 1; j < i; j++) {
				if (arr[i] > arr[j]) {
					dpLR[i] = Math.max(dpLR[j] + 1, dpLR[i]);
				}
			}
		} // 오른쪽에서 왼쪽으로 LIS 구하기
		int[] dpRL = new int[N + 1];
		for (int i = N; i > 0; i--) {
			dpRL[i] = 1;
			for (int j = N; j > i; j--) {
				if (arr[i] > arr[j]) {
					dpRL[i] = Math.max(dpRL[j] + 1, dpRL[i]);
				}
			}
		} // 두 dp 배열의 합의 최대값 찾기
		int max = 0;
		for (int i = 1; i <= N; i++) {
			max = Math.max(max, dpLR[i] + dpRL[i]);
		}
		System.out.println(max - 1); // 해당 원소 중복되므로 -1

	}
}