[Baekjoon] 11054_가장 긴 바이토닉 부분 수열

문제(출처: https://www.acmicpc.net/problem/11054)

---

< 가장 긴 바이토닉 부분 수열 >

 

문제 풀이 

 

좌측부터 증가하는 부분 수열을 구하고, 우측부터 증가하는 부분 수열을 구한다.

그러면 증가하는 부분 수열, 감소하는 부분 수열, 바이토닉 수열의 가장 긴 값을 구할 수 있다.

 

my solution (Java)

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

public class _11054_ { // 가장 긴 바이토닉 부분 수열

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

		int n = Integer.parseInt(bf.readLine());

		int a[] = new int[n];
		st = new StringTokenizer(bf.readLine());

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

		int dp1[] = new int[n];
		int dp2[] = new int[n];

		for (int i = 0; i < n; i++) {
			dp1[i] = 1;
			for (int j = 0; j < i; j++) {
				if (a[j] < a[i]) {
					dp1[i] = Math.max(dp1[i], dp1[j] + 1);
				}
			}
		}

		for (int i = n - 1; i >= 0; i--) {
			dp2[i] = 1;
			for (int j = n - 1; j > i; j--) {
				if (a[i] > a[j]) {
					dp2[i] = Math.max(dp2[i], dp2[j] + 1);
				}
			}
		}

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

		System.out.println(result);
	}

변수)
n : 수열 크기
a : 수열
dp1, dp2 : 증가하는 부분 수열, 감소하는 부분 수열
result : 가장 긴 바이토닉 수열의 길이 

 

수열 크기를 입력받는다. 수열 크기만큼 수열을 입력받아 배열 a에 저장한다. 좌측부터 증가하는 부분 수열을 구해 dp1에 저장하고, 우측부터 증가하는 부분 수열을 구해 dp2에 저장한다. dp1과 dp2를 탐색하며 최댓값을 구한다. 최종 result를 출력한다. 

---

---