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

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

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

 

cache1[i] 에 앞에부터 a[i]를 마지막으로 끝나는 수열 중 가장 긴 증가하는 수열의 길이를 저장하고, cache2[i] 에 뒤에부터 a[i]를 마지막으로 끝나는 수열 중 가장 긴 증가하는 수열의 길이를 저장한다. 이때 cache1,2를 채우는 방법은 bottom-up DP를 통해 채워나갔다. 그리고 만든 cache1과 cache2를 이용해서 가장 긴 바이토닉 부분 수열을 구했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
vector<int> a;
vector<int> cache1(1005, 1); //앞에부터 a[i]를 마지막으로 끝나는 수열 중 가장 긴 증가하는 수열의 길이
vector<int> cache2(1005, 1); //뒤에부터 a[i]를 마지막으로 끝나는 수열 중 가장 긴 증가하는 수열의 길이

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;

		a.push_back(input);
	}

	cache1[0] = 1;
	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= i - 1; j++) {
			//j에서 끝나는 증가하는 부분수열과 연결하는것 생각
			if (a[j] < a[i]) {
				cache1[i] = max(cache1[i], cache1[j] + 1);
			}
		}
	}

	cache2[n - 1] = 1;
	for (int i = n - 2; i >= 0; i--) {
		for (int j = i + 1; j <= n - 1; j++) {
			//j에서 끝나는 증가하는 부분수열과 연결하는것 생각
			if (a[j] < a[i]) {
				cache2[i] = max(cache2[i], cache2[j] + 1);
			}
		}
	}

	int result = 0;
	for (int i = 0; i < n; i++) {
		result = max(result, cache1[i] + cache2[i] - 1);
	}

	cout << result;

	return 0;
}