[baekjoon 11054] 가장 긴 바이토닉 부분 수열- DP(동적 프로그래밍) (C++)

 

www.acmicpc.net/problem/11054

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

이 문제를 풀기 전에 풀어보면 도움이 되는 두 문제이다.

 

www.acmicpc.net/problem/11722 가장 긴 감소하는 부분 수열

www.acmicpc.net/problem/11053 가장 긴 증가하는 부분 수열

 

바이토닉 수열이란 증가-> 감소하는 수열이라고 한다.

예를 들어 1, 2, 3, 4, 3, 2, 1의 경우 배열 자체가 바이토닉 수열이고 길이는 7이다. 증가만 해도 되고, 감소만 해도 된다.

 

처음에 풀었을 때는 

1) i번째까지의 최대 증가수열의 개수를 구하고

2) i번째부터 끝까지 최대 감소 수열의 개수를 구해서

3) 증가 개수 + 감소 개수 - 1의 최댓값을 저장했다.

 

0 ~ N-1일 때,

1. 인덱스 0~1 내에서 최대 증가수열 개수 + 1부터 N-1까지 최대 감소 수열(N^2 2중 for문)

2. 인덱스 0~2 내에서 최대 증가수열 개수 + 2부터 N-1까지 최대 감소 수열

... 

까지 거의 완전 탐색 느낌으로 더럽게(?) 풀었다.

 

결과에서 -1 해주는 이유는 I번째 수를 두 번 카운트하기 때문이다. 12321의 경우 123까지 3, 321까지 3 => 6 (실제는 5)

 

이렇게 풀게 되면 for문을 꽤 많이 돌려야 하고 제출할 때 시간 초과가 나올 줄 알았는데 0.596ms가 걸리고 통과했다.

하지만 코드가 별로라고 생각했고, for문도 많이 써서 나조차 코드를 잘 알아보기 힘들었다.

 

그래서 다른 분들의 풀이를 보다가 괜찮은 풀이를 찾았다.

 

해결방법은 위와 같이 0 ~ N-1까지 최대 증가수열을 구하되, 최대 감소 수열도 구한 뒤, i번째에서의 증가 + 감소를 구하는 방식이다.

 

i번째까지의 최대 증가수열은 0~i이고 인덱스 i번째에 저장된다.

하지만, 최대 감소 수열 또한 값이 저장되는 인덱스가 i고 어디서부터 i번째까지에서 감소 수열을 구한 것인지 모른다.

이 문제 때문에 감소 값의 범위를 정해줘야 한다고 생각하다 보니 위의 풀이가 나온 것이다.

 

저 아이디어를 해결하는 방법을 다른 풀이를 보다가 찾았다.

바로 감소 수열을 거꾸로 마지막 인덱스에서부터 구하는 것이다.

그렇게 하면 54321도 거꾸로 보면 12345가 되는 것처럼 우리가 원하는 바와 같이 인덱스 i에 증가하는 값(실제로는 감소하는 값)을 저장할 수 있게 된다.

 

그러면 결과적으로 각각 dpUp과 dpDown의 i번째에 0~i까지 최대 증가, i~N-1까지 최대 감소의 개수가 저장되는 것이다.

답을 구하기 위해서 for문을 돌면서 두 개의 배열[i]의 합-1이 가장 큰 것을 출력하면 된다.

#include <iostream>
using namespace std;

int arr[1001], dpUp[1001], dpDown[1001], N;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		dpUp[i] = 1;
		dpDown[i] = 1;
	}
	
	int result = 1;
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j] && dpUp[i] < dpUp[j] + 1) {
				dpUp[i] = dpUp[j] + 1;
			}
		}
	}

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

	for (int i = 0; i < N; i++) {
		result = max(result, dpUp[i] + dpDown[i]);
	}

	cout << result - 1;
}