[백준] 11054-가장 긴 바이토닉 부분 수열(C++)

문제링크:www.acmicpc.net/problem/11054

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

골드 3의 난이도는 아니였습니다. 다만 아이디어를 생각하는데 조금 어려움을 겪었습니다.

경우는 총 3가지 입니다.

 

올라갔다 다시 내려가는 경우 -> {10, 20, 30, 25, 20}

오름차순 ->{10, 20, 30, 40}

내림차순 ->{50, 40, 25, 10}

 

오름차순과 내림차순의 dp는 O(n^2)으로 쉽게 구할수 있습니다.

각각을 dp[i]와 dp_reverse[i]라고 하겠습니다.

 

올라갔다 내려가는 경우는 

dp[i] + dp_reverse[i] - 1 입니다. 해당 i에서의 오름차순 값 + 내림차순 값 - 1입니다. -1을 하는 이유는 자기자신이 두번 더해졌기 때문입니다. 

 

 

아래는 전체 정답코드입니다.

#include <iostream>
#include <cstring>
using namespace std;

int dp[1002];
int dp_reverse[1002];
int n = 0;
int arr[1001] = { 0, };
int result = 1;

void solve_forward() {

	for (int i = 2; i <= n; i++) {

		for (int j = i - 1; j >= 1; j--) {
			if (arr[j] < arr[i])
				if (dp[i] < dp[j] + 1)
					dp[i] = dp[j] + 1;

		}
	}
}
void solve_backward() {
	for (int i = n - 1; i >= 1; i--) {
		for (int j = i + 1; j <= n; j++) {
			if (arr[j] < arr[i])
				if (dp_reverse[i] < dp_reverse[j] + 1)
					dp_reverse[i] = dp_reverse[j] + 1;
		}

	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		dp[i] = 1;
		dp_reverse[i] = 1;
	}
	
	solve_forward();
	solve_backward();
	
	for (int i = 1; i <= n; i++) {

		if (dp[i] + dp_reverse[i] - 1 > result)
			result = dp[i] + dp_reverse[i] - 1;
		
		if (dp[i] > result)
			result = dp[i];
		else if (dp_reverse[i] > result)
			result = dp_reverse[i];
		
	}
	cout << result << endl;
	return 0;

}