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

 

 

 

<코드>

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

#define SIZE 1001

int n, tmp;
int A[SIZE];
int DP1[SIZE];
int DP2[SIZE];
int ans[SIZE];

int main()
{
	cin >> n;


	// 0에서 n-1까지
	for (int i = 0; i < n; i++)
	{	
		cin >> A[i];
		tmp = 0; // 가장 큰 tmp값을 찾기위해 0으로 초기화
		for (int j = 0; j < i; j++)
		{
			// 현재값(A[i])보다 작은 이전값들(A[j])중에서
			// 가장 큰 DP[j]값을 구하고 그 값을 tmp에 저장
			if (A[i] > A[j] && DP1[j] > tmp) tmp = DP1[j];
		}
		DP1[i] = tmp + 1; // 현재 수열 길이 +1 증가
		ans[i] += DP1[i];
	}


	// n-1에서 0까지
	for (int i = n-1; i >= 0; i--)
	{
		tmp = 0; // 가장 큰 tmp값을 찾기위해 0으로 초기화
		for (int j = n-1; j > i; j--)
		{
			// 현재값(A[i])보다 작은 이전값들(A[j])중에서
			// 가장 큰 DP[j]값을 구하고 그 값을 tmp에 저장
			if (A[i] > A[j] && DP2[j] > tmp) tmp = DP2[j];
		}
		DP2[i] = tmp + 1; // 현재 수열 길이 +1 증가
		ans[i] += DP2[i];
	}

	

	sort(ans, ans + n, greater<>()); // 내림차순 정렬

	cout << ans[0] - 1; // 최대값 출력

}

 

이전 포스트 - > 가장 긴 증가하는 부분 수열 LIS(Longest increasing subsequence) 구하는 방법과 예제

 

기존의 LIS구하는 방법을 응용하여

A[0]	A[1]	...	A[k]	...	A[n-2]	A[n-1]
DP[0]	DP[1]	...	DP[k]	...	DP[n-2]	DP[n-1]

DP1을 증가하는 수열이고 DP2를 감소하는 수열이라 할 때,
DP1[k] + DP2[k] 가 최대인 값이 가장 긴 바이토닉 부분 수열이 된다.

 

예제 입력 1을 예시로 들면

index	0	1	2	3	4	5	6	7	8	9
A[]	1	5	2	1	4	3	4	5	2	1
DP1[]	1	2	2	1	3	3	4	5	2	1
DP2[]	1	5	2	1	4	3	3	3	2	1
ans[]	2	7	4	2	7	6	7	8	4	2

A[0]부터 A[7]까지 증가하는 순열의 최대 길이가 5이고 A[9]에서 A[7]까지 증가하는 순열의 최대 길이는 3이다. 따라서 ans[]에서 가장 큰 값이 8이 가장 긴 바이토닉 부분 순열의 길이인데 여기서 A[7]이 중복으로 더해졌으므로 -1을 해준 7이 정답이 된다.

 

 

www.acmicpc.net/problem/11054

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