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

 

11053번 문제를 풀면 쉽게 접근할 수 있다.
https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

cf) 가장 긴 증가하는 부분 수열(11053)

앞에서부터 부분 길이를 채워나간다. 자신 앞의 (자신보다 작은)원소들 중 길이가 최대인 것을 가져와 +1을 하여 채워나간다.

void calc(int num) {
	sum[1] = 1;//처음 길이는 무조건 1
	for (int i = 2; i <= num; i++) {//앞에서부터 숫자를 갱신해 나감
		int m = 0;
		for (int j = i - 1; j > 0; j--) {//뒤를 탐색하며 
			if (arr[j] < arr[i]) {//자신보다 더 작고
				m = max(m, sum[j]);//최대인 길이
			}
		}
		sum[i] = m + 1;
	}
}

헤멘부분 -LIS)

"앞에서부터 훑으며 해당 item이 그 전 원소들보다 크다면 +1,
더 작은 원소가 나타난다면 해당 item보다 더 작은것을 찾아서 +1을 해준다."는 생각을 그대로 구현하려다보니 막혔다. 하지만 두 경우 모두 자기보다 작은 원소들 중 길이가 최대인 것에서 +1을 해주면 된다는 공통점이 있었다. 

 

 

이 문제의 경우 한 방향으로의 길이를 구하고 역방향으로의 길이를 구한후 합하는 방식으로 바이토닉 수열의 최대 길이를 구할 수 있다.  이때 (두 배열의 합 중 가장 큰 것 -1) 이 바이토닉 수열이  된다. -1을 하는 이유는 양 방향에서 구한 길이를 더하기 때문에 중복해서 더해지기 때문이다. 

 

#include<iostream>
using namespace std;
int arr[10002] = { 0, };//인덱스 밖의 item은 0, 길이도 0으로 하여 최소 길이 0
int sum[10002] = { 0, };//정방향 길이
int sum2[10002] = { 0, };//역방향 길이
int max(int a, int b) {
	if (a < b) {
		return b;
	}
	else
	{
		return a;
	}

}
void calc(int num) {
	sum[1] = 1;//처음 길이는 무조건 1
	for (int i = 2; i <= num; i++) {//앞에서부터 숫자를 갱신해 나감
		int m = 0;
		for (int j = i - 1; j > 0; j--) {//뒤를 탐색하며 
			if (arr[j] < arr[i]) {//자신보다 더 작고
				m = max(m, sum[j]);//선택시 더 큰 숫자를 만들 수 있으면 채택
			}
		}
		sum[i] = m + 1;
	}
}
void rcalc(int num) {
	sum2[num] = 1;
	for (int i = num - 1; i > 0; i--) {
		int m = 0;
		for (int j = i + 1; j <= num; j++) {
			if (arr[j] < arr[i]) {
				m = max(m, sum2[j]);
			}
		}
		sum2[i] = m + 1;
	}
}

int main() {
	int cnt;
	scanf("%d", &cnt);
	for (int i = 1; i <= cnt; i++) {
		scanf("%d", &arr[i]);
	}
	calc(cnt);
	rcalc(cnt);
	int ret = -1;
	for (int i = 0; i <= cnt; i++) {
		ret = max(ret, sum[i] + sum2[i] - 1);
	}
	printf("%d", ret);
}