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

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

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

---

문제 풀이

 바이토닉 수열은 LIS의 변형으로 커지면서 작아지는 부분 수열이다.

k번째를 기준으로 오르내림이 바뀌므로 정방향으로 LIS를 구하고 역방향으로 LIS를 구해서 DP 값을 따진다. 

여기서 주의할 점은 각 DP를 더한 값 중 가장 큰 값을 -1을 해야 한다는 점인데, 이유는 중복돼서 그렇다.

예를 들면, 문제 속 수열 { 1, 5, 2, 1, 4, 3, 4, 5, 2, 1 }에서 각 LIS는

정방향 : { 1, 2, 3, 4, 5 } / 역방향 : { 5, 2, 1 } 이다. 

이 숫자를 붙여서 나열하면 { 1, 2, 3, 4, 5, 5, 2, 1} 이라서 중복된 숫자 5를 한 번 빼야 한다. 

느낀 점

 문제를 접근할 때 K번째가 중요하다고 생각하고 둘을 어떻게 나눠서 접근할까 고민했는데 바로 맞는 접근법이었다. 코드가 LIS와 비슷한데 사람들이 많이 짜는 코드와 달랐어서 새로운 방식으로 코드를 구현해봤다. 개념 자체가 비슷해서 크게 다를 게 없었던 것 같다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, ans = 0;
int arr[1001], D[1001], P[1001];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		D[i] = 1;
		for (int j = 0; j < i;j++) {
			if (arr[i] > arr[j] && D[i] < D[j] + 1) {
				D[i] = D[j] + 1;
			}
		}
	}
	for (int i = n - 1; i >= 0;i--) {
		P[i] = 1;
		for (int j = n - 1;j > i;j--) {
			if (arr[i] > arr[j] && P[i] < P[j] + 1) {
				P[i] = P[j] + 1;
			}
		}
		ans = max(ans, D[i] + P[i]);
	}
	cout << ans - 1;
}