백준 11054 - 가장 긴 바이토닉 부분 수열(골드 3)

문제

백준 11054 - 가장 긴 바이토닉 부분 수열
(https://www.acmicpc.net/problem/11054)

접근법

처음에는 LIS(가장 긴 부분 증가 수열)을 구하고, LIS가 끝나는 부분의 인덱스를 시작으로 LDS(가장 긴 부분 감소 수열)을 구하려고 했다.
그리고 실제로 예제도 통과했으나

알고보니 반례가 있었다.
1 5 4 2 3 같은 경우, 내 접근법대로 하면 답이 3이 나오지만 이 문제에서의 답은 4이다.

그래서 LIS를 구하는 범위를 하나하나 정해가면서 바이토닉 수열이 최대가 되는 값을 찾는 완전탐색 방식을 생각했다.

구현

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int n;
int arr[1001];
int dp[1001];
int ans=0;
int ansindex=0;
int lis(int limit)//LIS 찾는 함수
{
	for(int i=1;i<=limit;i++)
	{
		dp[i]=1;
		for(int j=1;j<=i;j++)
		{
			if(arr[i]>arr[j])
				dp[i]=max(dp[i],dp[j]+1);
		}
			
	}
	
	int ret=0;
	for(int i=1;i<=limit;i++)
	{
		ret=max(ret,dp[i]);
	}
	return ret;
}
void lds(int limit,int ret) //LDS 찾는 함수
{
	for(int i=limit;i<=n;i++)
	{
		dp[i]=ret;
		for(int j=limit;j<=i;j++)
		{
			if(arr[i]<arr[j])
				dp[i]=max(dp[i],dp[j]+1);
		}
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&arr[i]);
	}

	for(int i=1;i<=n;i++)//모든 경우 탐색
	{
		memset(dp,0,sizeof(dp));
		int ret=lis(i);
		lds(i,ret);
		
		for(int j=1;j<=n;j++)
		{
			ans=max(dp[j],ans);
		}
	}

	
	printf("%d",ans);
	return 0;
}