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

🌽 문제

🥕 입출력

🥔 풀이

일단 골드4인거 보고 살짝 쫄아서
어제 풀었던 가장 긴 증가하는 부분 수열을 다시 풀어봤다.

바로 어제 풀어놓고 두 번 정도 틀려주기

이 문제의 핵심은
dp[i] = arr[i]로 끝나는 LIS의 길이로 두는 것이다.

바이토닉은 쭉 증가 or 쭉 감소 or 쭉 증가+쭉 감소 셋 중 하나를 만족해야 한다.
먼저 LIS 풀이 방식으로 쭉 증가하는 수열의 길이를 구할 수 있다.
조건을 반대로 걸면 arr[i]로 끝나는 감소하는 수열의 길이도 구할 수 있다.
문제는 어떤 수를 기준으로 왼쪽은 증가, 오른쪽은 감소하는 수열이어야 하기에,
arr[i]로 끝나는 감소하는 수열의 길이가 아니라
arr[i]로 시작하는 감소하는 수열의 길이가 필요하다.

아유 어뜨케 하나 고민하면서 그림판에 이리 저리 끄적여보던 거때
갑자기 번개를 맞았는지(아님)
뒤에서부터 거꾸로 비교해가면 되겠다는 해답을 얻었다!

그러니까 증가하는 수열의 길이를 구할 땐
i = 0 ~ (N - 1), j = 0 ~ (i - 1) 이런 for문을 돌도록 하고
반대로 감소하는 수열의 길이를 구할 땐
i = (N - 2) ~ 0, j = (N - 1) ~ (i + 1) 이런 for문을 돌도록 하는거다.

결국 증가/감소하는 배열의 길이를 각각 구한 다음
두 배열을 인덱스별로 합한 값에서 자기 자신을 제외(-1)한 값 중
최댓값을 출력하면 마무리된다.

🥬 코드

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

int arr[1001];
int incr[1001]; // incr[i]: arr[i]로 끝나는 가장 긴 증가하는 수열
int decr[1001]; // decr[i]: arr[i]로 시작하는 가장 긴 감소하는 수열

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	for (int i = 0; i < n; i++) {
		incr[i] = 1;
		decr[i] = 1;
	}

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[j] < arr[i]) {
				incr[i] = max({ incr[i], incr[j] + 1 });
			}
		}
	}

	for (int i = n - 2; i >= 0; i--) {
		for (int j = n - 1; j > i; j--) {
			if (arr[j] < arr[i]) {
				decr[i] = max({ decr[i], decr[j] + 1 });
			}
		}
	}
	
	int maxi = 0;
	for (int i = 0; i < n; i++)
		maxi = max(maxi, incr[i] + decr[i] - 1);
	cout << maxi;

	return 0;
}

🥜 채점

간만의 골드4 혼자 풀이 굉장한 뿌듯