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

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

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

풀이과정

 

부분 수열은 1, 2, 3, 2 1 과 같이 오름과 내림이 있는 수열을 말한다.

 

오름차순 수열과 내림차순 수열을 최대 길이를 구하여 문제를 풀었다.

 

오름차순은 dp[N] =  dp[1]....dp[N-1] 중 map[N] 값 보다 작으면서 젤 긴 수열을 찾아 +1을 해주었다.

 

내림차순은 뒤에서 시작했다. 특정 K값에서 내림차순으로 수열을 정의해야 K값이 겹치기 때문이다.

 

이제 dp[K] + dp2[K] 값 중 최댓값을 찾아 -1을 해주면 된다. K위치에서 겹치기 때문에 -1을 해준다.

 

소스코드

#include <stdio.h>

int map[1001];
int dp[1001];
int dp2[1001];
int N;

int solution()
{
	dp[0] = 1; //증가수열
	dp2[N-1] = 1; //감소수열
	int last = N - 1;
	int answer = 1;
	for (int i = 1; i < N; i++) {
		dp[i] = dp2[last - i] = 1;
		for (int j = 0; j < i; j++) {
			if (map[j] < map[i] && dp[i] < dp[j] + 1) {
				dp[i] = dp[j] + 1;
			}
			if (map[last - j] < map[last - i] && dp2[last - i] < dp2[last - j] + 1) {
				dp2[last - i] = dp2[last - j] + 1;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		int tmp = dp[i] + dp2[i] - 1;
		if (answer < tmp) {
			answer = tmp;
		}
	}
	return answer;
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &map[i]);
	}
	printf("%d\n", solution());
}