[알고리즘] 백준 11054번: 가장 긴 바이토닉 부분 수열 (C++), 메모이제이션 2번

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

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

(11055, 17216, 11722번은 다루지 않을 예정 >> 조금만 응용하면 되는 문제라 다룰 필요가 없다고 생각함.)

 

이 문제를 풀기 위해서는 어렵게 생각할 필요 없었다.

기존에 '가장 긴 증가하는 부분 수열 문제의 점화식에서 어떤 것을 추가해야 할까?'라는 생각으로 시작했다가 그럴 필요가 없다고 느껴졌다.

 

영감을 받은 문제가 있다.

https://draw-code-boy.tistory.com/51?category=963936 

[알고리즘] 백준 1149번: RGB거리 (C++), 점화식...

예전에 이 문제를 풀었던 게 이번 문제에 도움이 되었다. (한 번 풀어보길 추천한다.)

어떤 도움을 받았냐면 다음과 같은 생각을 할 수 있게 해주었다.

'한 번에 해결하기보다는 cache 배열을 하나 더 선언하면 쉽게 풀리지 않을까?'였다.

 

즉, 이게 무슨 소리냐면

'가장 긴 바이토닉 부분 수열 == 가장 긴 증가하는 부분 수열 + 가장 긴 감소하는 부분 수열 - 1'이라는 식이 떠올랐다는 소리다. -1을 해준 이유는 원소 하나가 겹치기 때문에 -1을 해주어야 답을 구할 수 있다. 

 

[AC 코드]

#include <iostream>
#include <algorithm>
using namespace std;

int arr[1001];
int cache[1001];
int cache2[1001];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	int maxValue = 0;
	for (int i = 1; i <= n; i++) {
		cache[i] = 1;
		for (int j = i - 1; j >= 1; j--) {
			if (arr[i] > arr[j]) {
				cache[i] = max(cache[i], cache[j] + 1);
			}
		}
	}

	for (int i = n; i >= 1; i--) {
		cache2[i] = 1;
		for (int j = i + 1; j <= n; j++) {
			if (arr[i] > arr[j]) {
				cache2[i] = max(cache2[i], cache2[j] + 1);
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		maxValue = max(maxValue, cache[i] + cache2[i] - 1);
	}

	cout << maxValue;
	return 0;
}