백준 11054 - 가장 긴 바이토닉 부분 수열 (C++)

문제

바이토닉 수열이란 다음의 조건을 만족하는 모든 수열을 의미한다.

 

수열 S가 어떤 수 S[k]를 기준으로 S[1] < S[2] < ... S[k - 1] < S[k] > S[k + 1] > ... S[N - 1] > S[N]

 

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

 

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ A[i] ≤ 1000)

 

예제 입력

10
1 5 2 1 4 3 4 5 2 1

 

예제 출력

7

 

문제 해결

어디서 힌트를 얻을 수 있을까?

 

가장 긴 바이토닉 부분 수열을 한번 잘 확인할 필요가 있다.

 

바이토닉 수열이란 결국 어떻게 보면 가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열을 합쳐놓을 꼴이다.

 

그렇기 때문에 각 index에 가장 긴 증•감하는 부분 수열의 길이를 구한 뒤 각 index를 더해주고 그 중 가장 큰 것을 구해주면 되는 것이다.

 

코드

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

int arr[1001];
int r_cache[1002];
int d_cache[1002];

int LIS(int N)
{
	int& ret = r_cache[N];
	if (ret != -1)
		return ret;
	ret = 1;
	for (int i = N - 1; i >= 0; i--)
	{
		if (arr[i] < arr[N])
			ret = std::max(ret, LIS(i) + 1);
	}
	return ret;
}

int LDS(int N, int size)
{
	int& ret = d_cache[N];
	if (ret != -1)
		return ret;
	ret = 1;
	for (int i = N + 1; i < size; i++)
	{
		if (arr[i] < arr[N])
			ret = std::max(ret, LDS(i, size) + 1);
	}
	return ret;
}

int main(void)
{
	int N;
	std::cin >> N;
	for (int i = 0; i < N; i++)
		std::cin >> arr[i];
	for (int i = 0; i <= N; i++)
	{
		r_cache[i] = -1;
		d_cache[i] = -1;
	}
	std::vector<int> ret(N, 0);
	for (int i = 0; i < N; i++)
	{
		LIS(i);
		LDS(i, N);
	}
	for (int i = 0; i < N; i++)
		ret[i] = r_cache[i] + d_cache[i] - 1;
	std::sort(ret.begin(), ret.end());
	std::cout << ret[N - 1] << std::endl;
	return 0;
}

 

문제 출처

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

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