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

백준 온라인 저지(BOJ) 11054번 가장 긴 바이토닉 부분 수열

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

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

* 사용언어 : C언어, C++

 

1. 문제

증가하다가 감소하는 수열을 바이토닉 수열이라고 할 때,

주어진 수열 A의 부분 수열 중 가장 긴 바이토닉 부분 수열의 길이를 출력

 

2. 풀이

백준 단계 별로 풀어보기의 직전 문제인 가장 긴 증가하는 부분 수열 문제를 풀어봤다면

약간의 아이디어만 더해서 쉽게 풀 수 있는 문제입니다.

https://rightbellboy.tistory.com/329

[백준/BOJ] 11053번 가장 긴 증가하는 부분 수열 (C/C++)

 

우선 큰 설계는 위 문제와 같습니다.

대신 이 문제는 증가하는 부분 수열의 길이를 저장하는 dp 배열을 2개 선언합니다.

첫 번째 배열(dp1)에는 1부터 N까지 증가하는 방향으로 구해서 저장하고,

두 번재 배열(dp2)에는 N부터 1까지 감소하는 방향으로 구해서 저장합니다.

 

그리고 dp1[i] + dp2[i] -1 중 가장 큰 값을 출력하면 끝입니다.

왜냐면 dp1은 1부터 i까지 가장 긴 증가하는 부분 수열의 길이이고,

dp2는 N부터 i까지 가장 긴 증가하는 부분 수열의 길이이기 때문입니다.

이 때, i번째의 숫자는 양 쪽 길이에 모두 포함되었으므로 1을 빼주어야 합니다.

 

저는 초기화 코드를 간결하게 하고 수열 중간에 1부터 다시 시작하는 Case를 처리하기 위해

dp 배열을 양쪽으로 1칸 씩 늘려서 그 값을 0으로 둔 채 그 공간까지 사용했습니다.

 

자세한 내용은 아래 코드 참고하시면 됩니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
11054_가장 긴 바이토닉 부분 수열
1124KB	4ms
*/
#include <cstdio>

const int LM = 1002;
int a[LM], dp1[LM], dp2[LM], N, max;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%d", &a[i]);

	for (int i = 1; i <= N; ++i) {
		for (int j = 0; j < i; ++j) {
			if (a[j] < a[i] && dp1[j] + 1 > dp1[i]) dp1[i] = dp1[j] + 1;
		}
	}

	for (int i = N; i > 0; --i) {
		for (int j = N + 1; j > i; --j) {
			if (a[j] < a[i] && dp2[j] + 1 > dp2[i]) dp2[i] = dp2[j] + 1;
		}
	}

	for (int i = 1; i <= N; ++i) {
		if (dp1[i] + dp2[i] > max) max = dp1[i] + dp2[i];
	}

	printf("%d\n", max - 1);
	return 0;
}