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

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 주어진 수열 중 가장 긴 바이토닉 수열을 구하는 문제입니다. 

 

바이토닉 수열이란 한 값을 기준으로 왼쪽은 증가하는 수열이고 오른쪽은 감소하는 수열을 이루는 형태를 말합니다. 

 

따라서 주어진 수열을 입력받고 수열의 첫번째 원소부터 돌면서 그 원소에서 가능한 가장긴 바이토닉 수열의 개수를 dp배열에 저장하면서 문제를 해결하여야 합니다. 완전 탐색으로 풀게 된다면 시간이 많이 걸리게 되므로 dp배열에 i인덱스에서 가능한 가장긴 수열의 개수를 저장해가면서 다음번에 그 인덱스에 저장된 값을 이용 하는 원리입니다. 

 

탐색을 할 때 다음으로 올 원소가 이전원소보다 크다면 증가하는 중이므로 true를 flag로 주고 감소한다면 false를 주면서 진행중인 수열이 감소하는 중인지 증가하는 중인지를 판별하여 가장 크기가 큰 바이토닉 수열을 찾을 수 있습니다.

 

다음은 코드입니다.

 

 #include <iostream>

using namespace std;

int N;
int arr[1001];
int dp[1001][2];
bool flag;
int maxnum;
int num;

int findfunc(int a, bool flag) {
	
	if(dp[a][flag] != 0)
		return dp[a][flag];
	
	for(int i = a+1; i < N; i++) {
		
		if(arr[a] < arr[i] && flag) 
			dp[a][flag] = max(dp[a][flag], findfunc(i, true));
		else if(arr[a] > arr[i]) {
			dp[a][flag] = max(dp[a][flag], findfunc(i, false));
		}
	}
	dp[a][flag]++;
	return dp[a][flag];
}


int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N;
	
	for(int i = 0; i < N; i++)
		cin >> arr[i];
	
	for(int i = 0; i < N; i++) {
		maxnum = max(maxnum, findfunc(i, true));
		maxnum = max(maxnum, findfunc(i, false));
	}
	
	
	cout << maxnum;
	return 0;
}