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

유형	난이도	완료일	링크	특이사항
DP	골드4	23/03/01	https://www.acmicpc.net/problem/11054

 

 

내 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
	int n;
	cin >> n;
	
	int arr[1000] = {};
	for(int i=0; i<n; i++)
		cin >> arr[i];
	
	int sum[2][1000] = {};
	
	sum[0][0]=1; 
	
	for(int i = 1; i<n; i++)
	{
		int max = 0;
		for(int j = i-1; j>=0; j--)
		{
			if(arr[j]<arr[i] && sum[0][j] > max)
			{
				max = sum[0][j];
			}
			sum[0][i] = 1 + max;
		}
	}	
	
	sum[1][n-1]=1;
	
	for(int i = n-2; i>=0; i--)
	{
		int descending = 0;
		for(int j = i+1; j<n; j++)
		{
			if(arr[j]<arr[i] && sum[1][j] > descending)
			{
				descending = sum[1][j];
			}
			sum[1][i] = 1+descending;
		}
	}
	
	int ans = 0;
	

	
	for(int i = 0; i<n; i++)
	{
		if(sum[0][i] + sum[1][i] > ans)
			ans = sum[0][i] + sum[1][i];
	}
	
	cout << ans-1;
	
}

11053번을 풀었던 기억으로 쉽게 풀 수 있었다. LIS해결 방법만 알고 있다면 내림차순 부분만 해결하면 된다.

바이토닉 수열은 오름차순-정점-내림차순 순서로 만들어진다. 물론 정점이 한 쪽 끝에 있다면 수열 내에 오름/내림차순만 존재할 수도 있다. LIS를 풀었던 방식과 동일하게 배열의 각 요소가 마지막 수(가장 큰 수)가 되었을 때의 오름차순 부분 수열의 길이를 누적하여 구하고 내림차순은 반대 방식으로 구한다.

오름차순이 i = 0부터 시작하여 i 앞 요소들과 크기를 비교하며 길이를 구했다면, 내림차순은 i = n-1부터 시작하여 i 뒤 요소들과 비교해서 내림차순 수열의 길이를 구한다. 방향만 다를 뿐 결국 똑같은 원리로 내림, 오름차순 길이를 모두 구하면 그 두 길이의 합이 가장 큰 지점이 바이토닉 수열의 정점이 되는 지점이다. 따라서 오름차순 길이 + 내림차순 길이 -1(정점이 두 번 더해지므로 한 번 빼준다)를 한 값이 정답이다.