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

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

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

 

난이도: solved.ac 골드 4

 

접근 방법

11053번을 풀었다면 아주 쉽게 풀 수 있는 문제다.

https://jangkunstory.tistory.com/37

[백준] 11053번: 가장 긴 증가하는 부분 수열

위 문제에서 사용한 코드를 그대로 사용하면 된다.

 

위의 알고리즘을 사용하면 len[i]에는 A[i]를 부분수열의 맨 끝 원소로 선택했을 때 가장 긴 길이가 저장되게 되는데, 이 문제에서는 이를 앞에서 한 번, 뒤에서 한 번 해주면 된다.

 

앞에서 한 번 하면 index = 0부터 N - 1까지 각 수마다 부분 수열의 최대 길이가 len1에 저장되고,

 

뒤에서 한 번 하면 index = N -1부터 0까지 부분수열의 최대 길이가 len2에 저장된다.

 

그리고 각 index별로 len1와 len2의 값이 가장 큰 값에서 1을 뺀 것을 출력하면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int A[1000], len1[1000], len2[1000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, i, j, ans = 0;
	cin >> N;
	for (i = 0; i < N; i++)
		cin >> A[i];
	for (i = 0; i < N; i++) {
		len1[i] = 1;
		for (j = 0; j < i; j++) {
			if (A[i] > A[j])
				len1[i] = max(len1[i], len1[j] + 1);
		}
	}

	for (i = N - 1; i >= 0; i--) {
		len2[i] = 1;
		for (j = N - 1; j > i; j--) {
			if (A[i] > A[j])
				len2[i] = max(len2[i], len2[j] + 1);
		}
	}
	for (i = 0; i < N; i++) {
		int sum = len1[i] + len2[i];
		if (sum > ans)
			ans = sum;
	}
	cout << ans - 1;
}

 

성능

코드 제출 결과