[백준 C++] 11054 가장 긴 바이토닉 부분 수열 - 다이나믹프로그래밍

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

#include <iostream>
using namespace std;

int Sequence[1000];
int LengthL[1000];
int LengthR[1000];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> Sequence[i];

		for (int j = 0; j < i; ++j)
		{
			if (Sequence[j] < Sequence[i]
				&& LengthL[j] > LengthL[i])
			{
				LengthL[i] = LengthL[j];
			}
		}

		LengthL[i] += 1;
	}

	for (int i = N; i >= 0; --i)
	{
		for (int j = i + 1; j < N; ++j)
		{
			if (Sequence[j] < Sequence[i]
				&& LengthR[j] > LengthR[i])
			{
				LengthR[i] = LengthR[j];
			}
		}

		LengthR[i] += 1;
	}

	int MaxLength = 0;
	for (int i = 0; i < N; ++i)
	{
		int Length = LengthL[i] + LengthR[i] - 1;
		if (Length > MaxLength)
		{
			MaxLength = Length;
		}
	}

	cout << MaxLength;
}

---

 

N의 크기가 크지 않기 때문에 DP를 이용해서 풀 수 있는 문제입니다.

증가하는 부분 수열의 길이와 감소하는 부분 수열의 길이를 DP 배열에 각각 저장한 후에

두 길이의 합이 가장 큰 수를 찾아서 해당 길이를 출력하면 됩니다.