백준 11054 가장 긴 바이토닉 부분 수열

 

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

 

서론

 

11053 문제에 비해 시간복잡도가 두배(+a) 늘었다. 그래서 같은 방식은 시간초과를 예상했으나 통과했다.

 

풀이

 

백준 11053 가장 긴 증가하는 부분 수열

 

위 문제에서 dp를 하나 더 추가한다.

 

기존이 1->n방향으로 증가시키는 dp1이였다면

n->1 방향으로 증가시키는 dp2를 만든다.

그 후 dp3[i] = dp1[i]+dp2[i] 한 뒤 dp3중 최대값-1을 출력한다.

 

예제 1, 5, 2, 1, 4, 3, 4, 5, 2, 1에서

가장 오른쪽 5의

dp1은 왼쪽에서부터 1, 5, 2, 1, 4, 3, 4, 5, 2, 1 의 5개를 저장하고

dp2는 오른쪽에서부터 1, 5, 2, 1, 4, 3, 4, 5, 2, 1 의 3개를 저장한다.

dp3은 5+3 = 8이고 5가 중복해서 들어가므로 -1 해준다.

 

구현

 

//c++

#include <iostream>
#include <algorithm>

using namespace std;

int dp[1002];
int dpR[1002];
int dpSum[1002];
int seq[1002];

int main() {
	int result = 0;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> seq[i];
		for (int j = 0; j < i; j++) {
			if (seq[j] < seq[i]) {
				if (dp[j] >= dp[i]) {
					dp[i] = dp[j] + 1;
				}
			}
		}
	}
	for (int i = n; i >= 1; i--) {
		for (int j = n + 1; j > i; j--) {
			if (seq[j] < seq[i]) {
				if (dpR[j] >= dpR[i]) {
					dpR[i] = dpR[j] + 1;
				}
			}
		}
		dpSum[i] = dp[i] + dpR[i];
	}
	cout << *max_element(dpSum, dpSum + 1002)-1;

}