[11054] 가장 긴 바이토닉 부분 수열

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

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

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

코드

#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <vector>

using namespace std;

int N;
vector<int> A;
int cache[1001][1001][2];

int LIS(int start, int before, int isDec){
	if(start == N){
		return 0;
	}
	
	int& ret = cache[start][before][isDec];

	if(ret != -1){
		return ret;
	}

	ret = 0;
	// 그냥 넘어갈 때
	ret = LIS(start+1, before, isDec);

	// 증가하고 있다면
	if(isDec == 0){
		if(before < A[start]){
			ret = max(LIS(start+1,A[start], 0)+1, ret);
		}
		else if(before > A[start]){
			ret = max(LIS(start+1, A[start], 1)+1, ret);
		}
	}

		//감소하고 있다면
	else if(isDec == 1){
		if(before > A[start]){
			ret = max(ret, LIS(start+1,A[start], 1)+1);
		}
	}

	return ret;
}

int main() {
  cin >> N;
	int ans = -1;

	memset(cache, -1, sizeof(cache));

	for(int i=0; i<N; ++i){
		int a;
		cin >> a;
		A.push_back(a);
	}

	cout << LIS(0, 0, 0);
	
  return 0;
}

몇시간 끙끙 앓다가 결국 답을 보고 푼 문제이다....  (답 출처 : https://sbl133.tistory.com/39)

여러가지 경우를 나눠서 풀어줬는데 cache 배열에 정보를 세개나 전달해줬다는게 좀 맘에 걸리긴 한다...

그냥 LIS문제의 코드에서 반복문을 쓴 걸 좀 활용해주면 더 간결하게 풀 수  있을 것 같은데 나중에 다시 해보고 좀 간결한 답이 나오면 재포스팅 해야겠다