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

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)

10
1 5 2 1 4 3 4 5 2 1

출력

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

7

풀이

다이나믹 프로그래밍을 사용하여 풀이하였습니다.

 

풀이 방식은 다음과 같습니다.

 

먼저 배열의 왼쪽부터 시작하여 두 수를 비교해가며 오른쪽에 있는 수(A)가 왼쪽에 있는 수(B)보다 더 클 경우 A의 dp값과 B의 dp값 + 1 을 비교하여 더 큰 쪽의 값으로 갱신시켜주었습니다.

 

마찬가지로 배열의 오른쪽부터 시작하여 두 수를 비교해가며 이번에는 왼쪽에 있는 수(A)가 오른쪽에 있는 수(B)보다 더 클 경우 A의 dp값과 B의 dp값 + 1 을 비교하여 역시 더 큰 쪽의 값으로 갱신시켜주었습니다.

 

즉, 배열의 양방향에서 오름차순으로 이루어지는 부분 수열의 길이만 구하여 저장한 것입니다.

 

마지막으로 출력값을 구할 때에는 위의 과정을 통해 구한 dp_left 배열과 dp_right 배열의 값을 각각의 인덱스끼리 모두 더한 뒤, 그 중에서 가장 큰 값으로 저장해주었습니다.

 

위와 같이 할 경우 자기 자신을 총 두 번 참조하기 때문에 중복이 한 번 발생하므로 최종적으로 값을 출력할 때에는 1을 뺀 값으로 출력해줍니다.

---

#include<iostream>

#define MAX 1000

using namespace std;

int n, ans = 0;
int arr[MAX];
int dp[MAX], dp_left[MAX], dp_right[MAX];

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

void solve()
{
	for (int i = 0; i < n; ++i) {
		dp_left[i] = 1;

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

	for (int i = n - 1; i > -1; --i) {
		dp_right[i] = 1;

		for (int j = n - 1; j > i; --j)
			if (arr[i] > arr[j])
				dp_right[i] = max(dp_right[i], dp_right[j] + 1);
	}

	for (int i = 0; i < n; ++i) {
		dp[i] = dp_left[i] + dp_right[i];

		ans = max(ans, dp[i]);
	}
		
	cout << ans - 1;
}

void init()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

int main()
{
	init();
	input();
	solve();

	return 0;
}