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

[문제 바로 가기] - 가장 긴 바이토닉 부분 수열

📌 유형 : dp

💡 아이디어

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

이 부분을 보자마자 어제 풀었던 연속합 2 문제랑 가장 긴 증가하는 부분 수열 4 문제의 풀이를 합치면 될 것 같다는 생각이 들었다.

순방향(왼->오)으로 탐색하는 dp1 배열과 역방향(오->왼)으로 탐색하는 dp2 배열을 이용해서 양방향에서 증가하는 수열의 최대 길이를 저장한다.

10
1 5 2 1 4 3 4 5 2 1

예제를 예로 들면 dp1은 [1 2 2 1 3 3 4 5 2 1]이 되고 dp2는 [1 5 2 1 4 3 3 3 2 1]이 된다.

이제 0부터 N-1까지 i번째 수를 기준으로 증가하고 감소할 수열의 최대 길이를 구하면 되는데 이때 dp1[i] + dp2[i]는 i번째 수가 2번 고려된 것이기 때문에 1을 빼주어야 답이 된다.

---

풀이

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

/**
 * 백준 11054번 가장 긴 바이토닉 부분 수열
 * - 양방향에서 증가하는 수열의 최대 길이를 세는 dp 배열 2개 사용
 */

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] nums = new int[N];
		
		for (int i = 0; i < N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] dp1 = new int[N]; // 왼 -> 오
		int[] dp2 = new int[N]; // 오 -> 왼
				
		dp1[0] = 1;
		for (int i = 1; i < N; i++) {
			dp1[i] = 1;
			for (int j = 0; j < i; j++) {
				if (nums[i] > nums[j]) {
					dp1[i] = Math.max(dp1[i], dp1[j] + 1);
				}
			}
		}
		
		dp2[N - 1] = 1;
		for (int i = N - 2; i >= 0; i--) {
			dp2[i] = 1;
			for (int j = N - 1; j > i; j--) {
				if (nums[i] > nums[j]) {
					dp2[i] = Math.max(dp2[i], dp2[j] + 1);
				}
			}
		}
		
		int answer = 0;
		for (int i = 0; i < N; i++) {
			answer = Math.max(answer, dp1[i] + dp2[i] - 1);
		}
		
		System.out.println(answer);
	}
	
}