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

www.acmicpc.net/problem/11054

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

백준 11053 - 가장 긴 증가하는 부분 수열 과 유사한 문제이다

 

바이토닉 수열이란 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN 를 만족하는 수열이다.

따라서 앞에서 뒤로 가는 방향으로 가장 긴 증가하는 부분 수열을 찾아서 dp_front에 저장해주고,

뒤에서 앞으로 가는 방향으로 가장 긴 증가하는 부분 수열을 찾아서 dp_back에 저장해준 다음,

dp_front[i] + dp_back[i] 가 최대가 되는 지점을 찾아주는 방법으로 문제를 해결했다.

 

이 때, dp_front[i]와 dp_back[i]는 항상 마지막 원소로 같은 값을 같기 때문에 겹치는 하나를 빼준다.

 

#include <iostream>

using namespace std;

int max(int a, int b) { return a > b ? a : b; }

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, max_val = 0;
	int arr[1000];
	int dp_front[1000] = { 0, };
	int dp_back[1000] = { 0, };

	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	fill(dp_front, dp_front + N, 1);
	fill(dp_back, dp_back + N, 1);
	for (int j = 1; j < N; j++) {
		for (int i = 0; i < j; i++) {
			if (arr[j] > arr[i]) dp_front[j] = max(dp_front[j], dp_front[i] + 1);
			if (arr[N - 1 - j] > arr[N - 1 - i]) dp_back[N - 1 - j] = max(dp_back[N - 1 - j], dp_back[N -1 - i] + 1);
		}
	}
	for (int i = 0; i < N; i++) max_val = max(max_val, dp_front[i] + dp_back[i]);
	cout << max_val - 1;
	return 0;
}

메모리: 2016 kb

시간: 0 ms