[Baekjoon/C++] 11054번 - 가장 긴 바이토닉 부분 수열

[백준] Baekjoon Online Judge

문제로 이동

 

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

 

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

---

풀이

#include <iostream>
using namespace std;

int N;
int arr[1000];
int dp[2][1000];

void increase();
void decrease();

void increase() {
	for (int i = 0; i < N; i++) {
		dp[0][i] = 1;

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

void decrease() {
	for (int i = N - 1; i >= 0; i--) {
		dp[1][i] = 1;

		for (int j = N - 1; j > i; j--) {
			if (arr[j] < arr[i])
				dp[1][i] = max(dp[1][i], dp[1][j] + 1);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];

	increase();
	decrease();

	int result = 0;
	for (int i = 0; i < N; i++)
		result = max(result, dp[0][i] + dp[1][i] - 1);

	cout << result << '\n';

	return 0;
}

 바이토닉 수열의 길이는 arr[i]로 끝나는 증가하는 수열과 arr[i]로 끝나는 감소하는 수열의 길이를 더한 것과 같다.

 

void increase() {
	for (int i = 0; i < N; i++) {
		dp[0][i] = 1;

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

 arr[i]로 끝나는 가장 긴 증가하는 수열의 길이를 구하는 함수이다.

 

void decrease() {
	for (int i = N - 1; i >= 0; i--) {
		dp[1][i] = 1;

		for (int j = N - 1; j > i; j--) {
			if (arr[j] < arr[i])
				dp[1][i] = max(dp[1][i], dp[1][j] + 1);
		}
	}
}

  arr[i]로 시작하는 가장 긴 감소하는 수열의 길이를 구하는 함수이다.

 

	int result = 0;
	for (int i = 0; i < N; i++)
		result = max(result, dp[0][i] + dp[1][i] - 1);

 위에서 구한 2개의 수열의 길이를 합친 것 중 가장 큰 것을 찾는 부분이다.