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

2022.01.16 - [프로그래밍/알고리즘] - [BOJ 11053] 가장 긴 증가하는 부분수열 - LIS

 

11053과 거의 흡사한 문제이다.

차이가 있다면 바이토닉 이라는 조건이 추가 된 것이다.

아래의 그림을 보도록 하자.

원소를 추가해가며 LIS를 만드는 것은 이전 문제와 같으나,

더 큰 원소가 들어왔을때에 바이토닉 배열을 갱신해준다.

N번째 원소보다 작은 것들로 이루어진 LIS의 배열의 크기를 LISLessThan[N] 이라고 하자. 

LIS를 만들며 이 배열을 갱신할 것이다.

1 2 3 4 5 6 에 7이 들어오면, LIS의 길이는 7이 되고, 이때에 LISLessThan[7] 은 7이 된다.

 

위 그림에서 빨간색으로 표시된 경우를 보도록 하자.

1 2 3 4 5 6 에 3이 들어오면, LIS는 길이는 그대로 6이고, 이때에 LISLessThan[7] 은 3이 된다.

왜 ? 들어온 원소 3보다 작은 원소는 몇개인지 찾아본다.

1과 2다. 들어온 원소 자기자신인 3을 포함해서 LISLessThan[7]은 3이 된다.

 

같은 방식으로 LIS를 구하는데, 뒤쪽의 원소부터 추가해가며 LIS를 만들어가면,

N에서 1로 진행하며 감소하는 수열을 만들어갈 수 있다.

이 값 또한 계속해서 갱신해준다.

 

코드는 다음과 같다.

마지막의 -3의 경우는, vector.back을 쓰기위해서 -1을 미리 넣어둔 것이다.

그래서 각각 -1씩 두번 -2,

또한 각 배열 LISLessThan 과 RLISBiggerThan은 자기자신을 포함한 값이 들어있다.

두번 적용되면 안되므로, -1을 해준다.

 

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

int Cost[1001] = { 0 , };
int LISLessThan[1001] = { 1 , };
int RLISBiggerThan[1001] = { 1 , };




int main()
{
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin.sync_with_stdio(false);
	std::cout.sync_with_stdio(false);

	int N;
	int MaxIdx = 0;

	std::cin >> N;

	std::vector<int> LIS;
	std::vector<int> RLIS;
	LIS.push_back(-1);
	RLIS.push_back(-1);


	LISLessThan[0] = 1;
	RLISBiggerThan[N] = 1;

	for (int i = 1; i <= N; ++i)
	{
		std::cin >> Cost[i];
		LISLessThan[i] = 1;
		if (Cost[i] > LIS.back())
		{
			LIS.push_back(Cost[i]);
			LISLessThan[i] = LIS.size();
		}

		else
		{	
			LISLessThan[i] = LISLessThan[i - 1];
			for (int k = 0; k < LIS.size(); ++k)
				if (LIS[k] >= Cost[i])
				{
					LISLessThan[0] = k + 1;
					LIS[k] = Cost[i];
					break;
				}
		}
			
	}

	for (int i = N; i >= 1; --i)
	{
		if (Cost[i] > RLIS.back())
		{
			RLIS.push_back(Cost[i]);
			RLISBiggerThan[i] = RLIS.size();
		}

		else
		{
			for (int k = 0; k < RLIS.size(); ++k)
				if (RLIS[k] >= Cost[i])
				{
					RLISBiggerThan[i] = k + 1;
					RLIS[k] = Cost[i];
					break;
				}
		}
			
	}

	int Res = 0;
	for (int i = 1; i <= N; ++i)
		Res = std::max(Res, LISLessThan[i] + RLISBiggerThan[i]);

	std::cout << Res - 3;

	return 0;
}