[알고리즘] 가장 긴 바이토닉 부분 수열 - 백준 11054

문제

가장 긴 증가하는 부분 수열의 응용 문제이다.

 

 

풀이

가장 긴 증가하는 부분 수열의 풀이 방법을 이용한다.

 

1. 배열의 시작점부터 가장 긴 증가하는 부분 수열의 풀이 방법을 이용하여 0 ~ idx까지의 증가하는 부분 수열의 길이를 구한다. 

2. 배열의 끝지점부터 가장 긴 증가하는 부분 수열의 풀이 방법을 이용하여 (배열의 크기 + 1) ~ idx까지 역순으로 증가하는 부분 수열의 길이를 구한다.

3. 구한 두 수열의 개수를 더하여 각 idx의 바이토닉 부분 수열의 길이를 구한다.

4. 가장 긴 바이토닉 부분 수열의 길이를 구한다.

 

표로 나타내면 아래처럼 된다.

idx	0	1	2	3	4	5	6	7	8	9	10	11
arr	0	1	5	2	1	4	3	4	5	2	1	0
right ->	0	1	2	2	1	3	3	4	5	2	1	0
left <-	0	1	5	2	1	4	3	3	3	2	1	0
dp	0	1	6	3	1	6	5	6	7	3	1	0

 

 

코드

#include<iostream>
using namespace std;

int arr[1002], rightDP[1002], leftDP[1002], DP[1002], n;

int solution()
{
	int rightMax = 0, leftMax = 0, maxDP = 0;

	for (int i = 1; i <= n; i++)
	{
		rightMax = 0;
		leftMax = 0;

		for (int j = 0; j < i; j++)
		{	
        	// 1. 오른쪽 방향 수열
			if(arr[j] < arr[i])
				rightMax = max(rightMax, rightDP[j]);
            // 2. 왼쪽 방향 수열
			if (arr[n + 1 - j] < arr[n + 1 - i])
				leftMax = max(leftMax, leftDP[n + 1 - j]);
		}

		rightDP[i] = rightMax + 1;
		leftDP[n + 1 - i] = leftMax + 1;
	}

	
	for (int i = 1; i <= n; i++)
	{
    	// 3. 바이토닉 수열 길이 구하기
		DP[i] = rightDP[i] + leftDP[i] - 1;
		
        // 4. 가장 긴바이토닉 수열 길이 구하기
		maxDP = max(maxDP, DP[i]);
	}

	return maxDP;
}

int main()
{
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	
	cout << solution();
}