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

 

#include <iostream>

using namespace std;

int DP[1001];
int DP2[1001];
int arr[1001];

int main(void)
{
	int A=0;
	
	cin>>A;
	
	for(int i=0; i<A; i++)
	{
		cin>>arr[i];
	}
	
	for(int i=0; i<A; i++)
	{
		for(int j=0; j<i; j++)
		{
			if(arr[i]>arr[j]&&DP[i]<DP[j]+1)
			{
				DP[i]=DP[j]+1;
			}
		}
	}
	
	for(int i=A-1; i>=0; i--)
	{
		for(int j=A-1; j>i; j--)
		{
			if(arr[i]>arr[j]&&DP2[i]<DP2[j]+1)
			{
				DP2[i]=DP2[j]+1;
			}
		}
	}
	
	int max=0;
	for(int i=0; i<A; i++)
	{
		if(DP[i]+DP2[i]+1>max)
		{
			max=DP[i]+DP2[i]+1;
		}
	}
	
	
	cout<<max;
	
	
	
	return 0;
 }

가장 긴 바이토닉 수열을 찾아서 길이를 출력하는 문제이다.

 

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

예)

1->2->5->4->2->1 

1->2->5

5->3->1

 

문제 해결 방법

1.왼쪽에서 증가하는 수열의 길이를 구한다.

2.오른쪽에서 증가하는 수열의 길이를 구한다.

 

두개의 합 중 가장 큰 합+1을 출력해주면 된다.(+1은 자기 자신을 의미한다.)

2+3+1=6