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

문제는 다음과 같습니다.

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

 

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

S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN

이렇게 생긴 수열을 바이토닉 수열이라고 합니다. 

즉, 사진에 표시해 놓은 것 처럼 k를 꼭지점으로 하고 시작지점에서부터 k까지는 증가수열, k부터 끝지점까지는 감소수열 형태인것입니다. 

 

풀이 방법 

array[] : 입력값 수열 A

increase[] : 시작점부터 해당 지점까지의 증가부분수열의 최대길이

decrease[] : 해당 지점부터 끝지점까지의 감소부분수열의 최대길이 

바이토닉 수열이 시작점부터 k까지의 증가수열과 k부터 끝지점까지의 감소수열이 합쳐진 모양이기 때문에 각각을 따로 구해야합니다. 배열의 모든 원소가 꼭지점 k가 될 수 있으므로 k=1 일 때, k=2 일 때, ... , k=n 일 때 증가부분수열의 최대길이를 increase 배열에, 감소부분수열의 최대길이를 decrease 배열에 저장합니다.

꼭지점 k는 increase 배열, decrease 배열에 둘 다 들어가기 때문에 increase[k] + decrease[k] - 1 이 꼭지점이 k 인 바이토닉 부분수열의 최대길이가 됩니다. 따라서 k=1 일 때, k=2 일 때, ... , k=n 일 때 바이토닉 부분수열의 최대길이를 비교하였을 때 가장 큰 값이 문제의 답이 됩니다.

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

int main()
{
	int increase[1001];
	int decrease[1001];
	int array[1001];
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> array[i];

	//처음부터 해당 위치까지 증가부분수열 최대크기
	for (int i = 1; i <= n; i++) {
		increase[i] = 1;
		for (int j = 1; j < i; j++) {
			if (array[j] < array[i])increase[i]=max(increase[i], increase[j] + 1);
		}
	}
	//해당 위치부터 끝까지 감소부분수열 최대크기
	for (int i = n; i >=1; i--) {
		decrease[i] = 1;
		for (int j = n; j > i; j--) {
			if (array[j] < array[i])decrease[i]=max(decrease[i], decrease[j] + 1);
		}
	}

	//답 찾기
	int answer = 0;
	for (int i = 1; i <= n; i++) {
		int temp = increase[i] + decrease[i];
		if (answer < temp)answer = temp;
	}
	cout << answer - 1;
	return 0;
}

 해당 위치까지 증가부분수열의 최대길이를 구하는 알고리즘은 다음과 같습니다.

• increase[i]의 값을 구한다고 할 때, 증가부분수열에 i 만 포함되는 경우는 반드시 있으므로 increase[i]=1로 초기화 시켜놓는다.
• 그리고 j 중에 i보다 작은 값이 있으면 i가 증가부분수열에 포함될 수 있으므로 increase[j]+1 이 increase[i]의 후보값이 된다. 후보값 중 가장 큰 값이 increase[i]가 된다.

감소부분수열의 최대길이도 같은 방법으로 구하면 됩니다.