(백준/C++) 11053_가장 긴 바이토닉 부분 수열

가장 긴 바이토닉 부분 수열 문제를 풀기 전에 가장 긴 증가하는 부분 수열 문제를 풀고 오는 것을 추천 드립니다.

11053번: 가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열 풀이

바이토닉 수열은 어떤 수열이 증가하다가 감소하는 형태를 갖는 수열입니다.

즉, 증가하다가 감소하게 되는 부분 수열들 중 가장 긴 값을 찾아야 합니다.

우선, 동적 계획법(Dynamic Programming, DP)이란, 큰 문제를 작은 문제들로 나누어 풀어나가고 작은 문제의 해를 저장해 다시 계산하지 않고 사용하는 방식입니다.

동적 계획법 문제는 최적 부분 구조와 중복된 부분 문제의 두 가지 속성을 가집니다. 이 두 가지 속성에 대해서 생각해보고 가겠습니다.

1. 최적 부분 구조: 가장 긴 바이토닉 부분 수열 문제에서 최적 부분 구조는 다음과 같이 두 부분으로 나뉠 수 있습니다.
   1. 증가 부분 수열: 각 요소에서 이전 요소들과 비교하여 증가하는 부분 수열의 최대 길이를 찾습니다.
   2. 감소 부분 수열: 각 요소에서 이후 요소들과 비교하여 감소하는 부분 수열의 최대 길이를 찾습니다.

   즉, 바이토닉 수열의 길이를 최대화하려면, 특정 위치에서의 증가하는 부분 수열의 최대 길이와 감소하는 부분 수열의 최대 길이를 결합하여 계산해야 합니다.

2. 중복된 부분 문제: 각 요소에 대해 이전/이후 요소들과의 최대 길이를 계산할 때, 이전에 이미 계산한 결과를 재사용하게 됩니다.

---

접근법

1. 초기화

이 문제에서도 각 요소를 첫 번째로 시작하는 부분 수열이라면 길이가 1이기 때문에 1로 초기화합니다.

2. 점화식 찾기

이 문제는 점화식을 두 개 찾을 수 있습니다.

증가하는 부분 수열의 경우에는 현재 요소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 구해야 합니다. 이는 i번째 요소보다 작은 모든 이전 요소(j < i)에 대해 가장 긴 부분 수열의 길이를 찾아야 합니다

반대의 경우에도 마찬가지로 현재 요소를 시작으로 하는 가장 긴 감소하는 부분 수열의 길이를 구해야 합니다.

---

풀이

만약 가장 긴 증가하는 부분 수열 문제를 풀고 왔다면 어렵지 않게 점화식을 찾고, 문제를 풀 수 있을 겁니다.

#include <iostream>
#include <vector>
using namespace std;
vector<int> seq;
vector<vector<int>> length;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;
	seq.resize(N);
	length.resize(N, vector<int>(2, 1));

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

	//i를 마지막으로 하는 제일 긴 수열을 계산한다.
	for (int i = 1; i < N; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (seq[i] > seq[j])
				length[i][0] = max(length[i][0], length[j][0] + 1);
		}
	}

	//i를 시작으로 하는 제일 긴 수열을 계산한다.
	for (int i = N - 1; i >= 0; i--)
	{
		for (int j = N - 1; j > i; j--)
		{
			if (seq[i] > seq[j])
				length[i][1] = max(length[i][1], length[j][1] + 1);
		}
	}

	int lengthMax = 0;
	for(int i = 0; i < N; i++)
	{
		lengthMax = max(lengthMax, length[i][0] + length[i][1] - 1);
	}

	cout << lengthMax;
}

---

참고

가장 긴 증가하는 부분 수열 풀이