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

[문제 링크]

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

---

얼핏 보기엔 복잡하고 어려워보이는 문제였지만, LIS와 LDS를 구하는 dp함수를 구현하면 간단히 풀 수 있는 문제였다.

 

중심점 here을 기준으로 arr[1] ~ arr[here] 까지 LIS + arr[here] ~ arr[N] 까지 LDS - 1 이 바이토닉 부분 수열의 길이가 되고, 중심점 here을 1~N으로 했을 때 가장 큰 값이 문제의 정답이 된다.

---

#include <iostream>
using namespace std;

int N, arr[1001], LIS[1001], LDS[1001];

int max(int a, int b) { return a > b ? a : b; }

int Topdown_LIS(int here)
{
	int& ret = LIS[here];
	if (ret != 0) return ret;

	ret = 1;

	for (int i = 1; i < here; i++)
		if (arr[i] < arr[here])
			ret = max(ret, Topdown_LIS(i) + 1);
	
	return ret;
}

int Topdown_LDS(int here)
{
	int& ret = LDS[here];
	if (ret != 0) return ret;

	ret = 1;

	for (int i = here + 1; i <= N; i++)
		if (arr[i] < arr[here])
			ret = max(ret, Topdown_LDS(i) + 1);

	return ret;
}

int Bottomup_LIS(int here)
{
	for (int i = 1; i <= here; i++)
	{
		LIS[i] = 1;
		for (int j = 1; j < i; j++)
			if (arr[i] > arr[j])
				LIS[i] = max(LIS[i], LIS[j] + 1);
	}

	return LIS[here];
}

int Bottomup_LDS(int here)
{
	for (int i = N; i >= here; i--)
	{
		LDS[i] = 1;
		for (int j = i + 1; j <= N; j++)
			if (arr[i] > arr[j])
				LDS[i] = max(LDS[i], LDS[j] + 1);
	}

	return LDS[here];
}

int main(void)
{
	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> arr[i];
	
	// top-down
	int res = 1;
	for (int i = 1; i <= N; i++)
		res = max(res, Topdown_LIS(i) + Topdown_LDS(i) - 1);
	cout << res << endl;
	
	// bottom-up
	res = 1;
	for (int i = 1; i <= N; i++)
		res = max(res, Bottomup_LIS(i) + Bottomup_LDS(i) - 1);
	cout << res << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 88 day