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

김두현·2022년 11월 10일

목록 보기

20/133

🔒[문제 url]

https://www.acmicpc.net/problem/11054

🔑알고리즘

가장 긴 증가하는 부분 수열
가장 긴 감소하는 부분 수열
위 두 문제가 교배된 문제였고, 마찬가지로 Dynamic Programming으로 해결할 수 있다.

S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN의 형태는 즉,
Sk를 기준으로 증가하는 부분 수열과 감소하는 부분 수열이 이어져있는 형태임을 알 수 있다.

어떻게 바이토닉 수열의 최장 길이를 구할 수 있을까?

k번째 원소까지의 증가하는 부분 수열과 , k번째 원소부터 n번째 원소까지의 감소하는 부분 수열의 합이 최대가 되는 부분이 최장 길이가 됨을 알 수 있다.

가장 긴 증가하는 부분 수열을 구하는 알고리즘을 배열의 역방향으로 적용하면, 가장 긴 감소하는 부분 수열이 됨을 알 수 있다.

즉, dp 배열을 두 개 생성해 가장 긴 증가하는 부분 수열의 알고리즘을 배열의 정방향과 역방향으로 적용하고, 두 dp 배열의 i번째 값의 합이 최대값이 정답이 된다.

dpGreater[x] : x번째 원소까지의 가장 긴 증가하는 부분 수열

dpLess[x] : x번째 원소 이후로 가장 긴 감소하는 부분 수열

가장 긴 증가하는 부분 수열은 어떻게 구하는가?

i번째 원소에서의 가장 긴 증가하는 부분 수열dp[i]은,
0번째 원소부터 i - 1원소까지의 dp값 중 최대값dp[j] + 1이며, 증가하는 부분 수열이므로 당연히 A[i] > A[j]이어야한다.

이러한 알고리즘으로 예시 입력1의 dp값을 구하면 이렇게 된다.
이때, 가장 긴 증가하는 부분 수열의 끝 원소과 가장 긴 감소하는 부분 수열의 첫 원소는 중복되므로, 출력 시 1을 빼준다.

🐾부분 코드

// 초기 작업
dpGreater[0] = 1; dpLess[n - 1] = 1;

// Bottom Up Dynamic Programming
for (int i = 1; i < n; i++)
{
	int maxDP_greater = 1; int maxDP_less = 1;
	for (int j = 0; j < i; j++)
	{
		if (A[i] > A[j])
		{// dpGreater
			maxDP_greater = max(maxDP_greater, dpGreater[j] + 1);
		}
		if (A[n - 1 - i] > A[n - 1 - j])
		{// dpLess
			maxDP_less = max(maxDP_less, dpLess[n - 1 - j] + 1);
		}
	}
	dpGreater[i] = maxDP_greater;
	dpLess[n - 1 - i] = maxDP_less;
}

<dp 배열 채우기>
dpGreater[0]을 1로,
dpLess은 역방향 갱신이므로 dpLess[n - 1] = 1로 초기화한다.
가장 긴 증가하는 부분 수열을 구하는 알고리즘을
dpGreater에는 정방향, dpLess에는 역방향으로 적용한다.

// i번째 원소에서의 (증가하는 수열) + (감소하는 수열)의 최대값 찾기
int ans = 1;
for (int i = 0; i < n; i++)
	ans = max(ans, dpGreater[i] + dpLess[i]);
    
// 기준 원소 중복 빼주기 (S_k)
cout << ans - 1;

<정답 탐색 및 출력>
위에서 설명한 알고리즘에 따라 dp값의 합이 최대인 것에 중복되는 원소의 길이 1을 빼주고 출력한다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <algorithm>
#include <cmath>
using namespace std;

int n;
int A[1001];
int dpGreater[1001], dpLess[1001]; // 증가하는 수열, 감소하는 수열

void INPUT()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> A[i];
}

void SOLVE()
{
	// 초기 작업
	dpGreater[0] = 1; dpLess[n - 1] = 1;
	
	// Bottom Up Dynamic Programming
	for (int i = 1; i < n; i++)
	{
		int maxDP_greater = 1; int maxDP_less = 1;
		for (int j = 0; j < i; j++)
		{
			if (A[i] > A[j])
			{// dpGreater
				maxDP_greater = max(maxDP_greater, dpGreater[j] + 1);
			}
			if (A[n - 1 - i] > A[n - 1 - j])
			{// dpLess
				maxDP_less = max(maxDP_less, dpLess[n - 1 - j] + 1);
			}
		}
		dpGreater[i] = maxDP_greater;
		dpLess[n - 1 - i] = maxDP_less;
	}

	// i번째 원소에서의 (증가하는 수열) + (감소하는 수열)의 최대값 찾기
	int ans = 1;
	for (int i = 0; i < n; i++)
		ans = max(ans, dpGreater[i] + dpLess[i]);

	// 기준 원소 중복 빼주기 (S_k)
	cout << ans - 1;
}

int main()
{
	INPUT();

	SOLVE();
}