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

문제

수열 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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

---

가장 긴 증가하는 부분 수열과 감소하는 부분 수열을 섞은 것 같은 문제이다.

다만 주의할 점은 감소하는 부분 수열을 그대로 구하면 안 되고 거꾸로 증가하는 부분 수열을 찾아야 한다.

 

예를 들어 p = {30, 20, 10} 이라는 배열이 있을 때 감소하는 부분 수열을 구하면 dp = {1, 2, 3}이 된다. 

이때 거꾸로 증가하는 부분 수열을 구하면 dp = {3, 2, 1}이 되므로 바이토닉 부분 수열에 적용할 수 있다.

 

다시 예를 들어서 p = { 10, 20, 30, 15, 5 } 라고 하면, 가장 긴 증가하는 부분 수열 dp = { 1, 2, 3, 2, 1 }이고

거꾸로 증가하는 부분 수열 rdp = { 2, 3, 3, 2, 1 }이 된다. 따라서 이 두 배열을 이용해 가장 긴 바이토닉 부분 수열을 구하면 res = dp[i] + rdp[i] - 1이 최대가 되는 값이다. p가 30일때 두 값을 더하면 5로 가장 길어지므로 정답은 5가 된다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EA%B0%80%EC%9E%A5%20%EA%B8%B4%20%EB%B0%94%EC%9D%B4%ED%86%A0%EB%8B%89%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4%20(11054%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <algorithm>
using namespace std;
int N;
int p[1001];
int dp[1001];
int rdp[1001];

int main()
{
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> p[i];

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

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

	int res = 1;
	for (int i = 1; i <= N; i++) {
		res = max(res, dp[i] + rdp[i] - 1);
	}

	cout << res;
}