[c++/백준] 11054번: 가장 긴 바이토닉 부분 수열

문제 링크

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

풀이

다이나믹 프로그래밍을 이용하는 문제

1. 먼저 base를 기준으로 가장 긴 증가하는 수열과 감소하는 수열을 찾아야한다.
2. dp1은 증가하는 수열, dp2는 감소하는 수열의 길이를 저장한다.
   2-1. 증가하는 수열은 밑의 표처럼 정리될 것이다.

i	0	1	2	3	4	5	6	7	8	9
수	1	5	2	1	4	3	4	5	2	1
dp1	1	2	2	1	3	3	4	5	2	1

3. 구한 dp1과 dp2를 가지고 ans를 구하는데, base번째 값은 중복되기 때문에 -1을 해준다.
4. ans를 정렬해주고 출력한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<int> v;
	for (int i = 0;i < n;i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	vector<int> ans(n);
	vector<int> dp1(n,1);
	vector<int> dp2(n,1);
	for (int base = 0;base < n;base++) { //base를 기준으로
		for (int i = 1;i <= base;i++) { //증가 수열
			for (int j = 0;j < i;j++) {
				if (v[i] > v[j]) {
					dp1[i] = max(dp1[j] + 1, dp1[i]);
				}
			}
		}
		for (int i = n - 2;i >= base;i--) { //감소 수열
			for (int j = n - 1;j > i;j--) {
				if (v[i] > v[j]) {
					dp2[i] = max(dp2[j] + 1, dp2[i]);
				}
			}
		}
		ans[base] = dp1[base] + dp2[base] - 1;
	}

	sort(ans.begin(), ans.end(), greater<int>());

	cout << ans[0];

	return 0;
}