[동적계획법 1 단계] 백준 11054번 가장 긴 바이토닉 부분 수열 oo

문제

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

 

 

차근 차근 생각해보는것이 최고인 듯.

4 5 2 5 4 1 8

2를 중심으로 생각해보면 2를 앞으로는 증가 2를 뒤로는 감소 수열이여야 한다.

2를 포함한 앞과 2를 포함한 뒤로 영역을 분리한다.

 

2가 중심좌표이므로 2는 수열에 반드시 포함된다.

따라서 

4 5 2 에서 증가 수열을 생각하면 2보다 작은 수가 없으므로 1

증가 수열의 인덱스를 up[] 에다가 담는다고 하면 그 값은 up[2] 즉, 중심좌표 인덱스에 저장된다.

2 5 4 1 8 에서 감소 수열을 생각하면

2보다 작은 것은 1밖에 없으므로 길이 2

하지만 감소 수열 같은 경우는 down[2] 혹은 down[N-1]이 아니라 어떤 max값을 갖는 인덱스인 down 5에 저장된다.

따라서 증가 수열은 up[i] + down의 맥스 값에서 2가 중복으로 증가 수열과 감소 수열에서 모두 세고 있으므로 1을 빼주면 답이 됨.

 

 

 

#include <iostream>
#include <vector>
#include<queue>
#include <string.h>
#include <map>
#include<algorithm>
using namespace std;

int up[1001];
int down[1001];
int arr[1001];

int main() {
	int N;
	cin >> N;


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

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

		int max_down = 0;
		for (int j = i; j <= N; j++)
		{
			down[j] = 1;
			for (int k = i; k < j; k++)
			{
				if (arr[j] < arr[k] && down[j] < down[k] + 1)
				{
					down[j] = down[k] + 1;
				}
			}
			if (max_down < down[j])
			{
				max_down = down[j];
			}
		}
		int ans = up[i] + max_down - 1;
		if (maxa < ans)
		{
			maxa = ans;
		}
	}
	cout << maxa << endl;

}