[백준] 동적 계획법 - 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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

이 문제를 풀기 위해서는 가장 긴 증가하는 부분 수열(풀이)을 먼저 풀어보기 바란다.

가장 긴 증가하는 부분수열은 증가하는 부분 수열을 찾는 것이라면, 바이토닉 부분수열은 증가하다 감소하는 수열 중 가장 긴 값을 찾는 것이다. (증가만, 감소만, 증가하다 감소)

문제의 예시로 풀이를 해보겠다.

증가만 하는 수열 // ->

1	5	2	1	4	3	4	5	2	1
1	2	2	1	3	3	4	5	2	1

dp[0] ={1}

dp[1] ={1, 5}

dp[2] ={1, 2}

dp[3] ={1}

dp[4] ={1, 2, 4}

dp[5] ={1, 2, 3}

dp[6] ={1, 2, 3, 4}

dp[7] ={1, 2, 3, 4, 5}

dp[8] ={1, 2}

dp[9] ={1}

감소만 하는 수열(오른쪽에서 증가하는 수열) // <-

1	5	2	1	4	3	4	5	2	1
1	5	2	1	4	3	3	3	2	1

dp[0] ={1}

dp[1] ={1, 2, 3, 4, 5}

dp[2] ={1, 2}

dp[3] ={1}

dp[4] ={1, 2, 3, 4}

dp[5] ={1, 2, 3}

dp[6] ={1, 2, 4}

dp[7] ={1, 2, 5}

dp[8] ={1, 2}

dp[9] ={1}

가장 긴 바이토닉 수열은 어떻게 구하는가? 두 수열의 결과를 더하면 된다.

입력	1	5	2	1	4	3	4	5	2	1
증가	1	2	2	1	3	3	4	5	2	1
감소	1	5	2	1	4	3	3	3	2	1
합	2	7	4	3	7	6	7	8	4	2

우리가 원하는 결과는 7이다. 그런데 왜 7인가? 가장 많은 수를 찾으면 되나? 아니다.

합에서는 해당 입력이 두 번씩 들어간다. 그래서 결과에서 1 씩 빼주어야 진짜 결과이다.

그래서 최댓값인 8에서 1을 빼준 7이 진짜 답이다.

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.StringTokenizer;
	// 가장 긴 바이토닉 부분 수열
	public class Main {
	static int n;
	static int[] arr, dp1, dp2;
	static void input() throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	n = Integer.parseInt(br.readLine());
	arr = new int[n + 1];
	dp1 = new int[n + 1];
	dp2 = new int[n + 1];
	StringTokenizer st = new StringTokenizer(br.readLine());
	for (int i = 1; i <= n; i++)
	arr[i] = Integer.parseInt(st.nextToken());
	}
	static void dp() {
	for (int i = 1; i <= n; i++) {
	dp1[i] = 1;
	for (int j = 1; j < i; j++) {
	if (arr[i] > arr[j] && dp1[i] <= dp1[j]) {
	dp1[i] = dp1[j] + 1;
	}
	}
	}
	for (int i = n; i > 0; i--) {
	dp2[i] = 1;
	for (int j = n; j > i; j--) {
	if (arr[i] > arr[j] && dp2[i] <= dp2[j]) {
	dp2[i] = dp2[j] + 1;
	}
	}
	}
	int max = Integer.MIN_VALUE;
	for (int i = 1; i <= n; i++) {
	max = Math.max(max, dp1[i] + dp2[i]);
	}
	System.out.println(max - 1);
	}
	public static void main(String[] args) throws IOException {
	input();
	dp();
	}
	}

view raw A11054.java hosted with ❤ by GitHub