Problem 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 (1 ≤ N ≤ 1,000)이 주어진다.

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

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

문제 링크

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

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

solve

d[n] = a[1]…a[n]에서 a[n]으로 끝나는 증가하는 부분수열
d2[n] = a[n]에서 시작하는 감소하는 부분수열의 길이
- 여기서 d2[n]은 a[n]부터 시작하므로 i를 n부터 감소시키며
- j를 i가 지나온 수들로 하여 가장 긴 값에 +1 하여 d2[i]에 대입한다.
d[n]과 d2[n]을 각각 구하여 (d[i] + d2[i] - 1)의 최댓값을 구하면 된다
- 이때, n이 두 번 나오므로 1을 빼준다

코드 설명

#include<iostream>
#include<algorithm>
using namespace std;
int a[1001];
int d[1001]; // d[n] = a[1]...a[n]에서 a[n]으로 증가하는 부분수열
int d2[1001]; // d2[n] = a[n]에서 시작하는 감소하는 부분수열의 길이
int main(void)
{
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> a[i];

	for (int i = 1; i <= n; i++) // d[n] = a[n]으로 끝나는 증가하는 부분수열
	{
		d[i] = 1;
		for (int j = 1; j < i; j++)
		{
			if (a[i] > a[j] && d[i] < d[j] + 1)
				d[i] = d[j] + 1;
		}
	}

	for (int i = n; i >= 1; i--)  // d2[n] = a[n]으로 시작하는 감소하는 부분수열
	{		 // a[n]으로 시작해야하기 때문에 반대로 감소시키며 비교한다
		d2[i] = 1;
		for (int j = i + 1; j <= n; j++)
		{
			if (a[i] > a[j] && d2[i] < d2[j] + 1)
				d2[i] = d2[j] + 1;
		}
	}

	int result = 0;
	for (int i = 1; i <= n; i++)
		result = max(result, d[i] + d2[i] - 1); // n이 겹쳐서 두번 나오기 때문에 1을빼준다
	cout << result << '\n';
}

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

Baekjoon algorithm