#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)

풀이:

• 이 문제는 #11053: 가장 긴 증가하는 부분 수열의 응용 문제라고 생각하면 된다. 따라서 이 문제를 풀기 전에 #11053: 가장 긴 증가하는 부분 수열 문제를 풀어보고 풀이도 읽어보고 이 문제를 풀기를 바란다. 이 문제와 #11053: 가장 긴 증가하는 부분 수열의 차이점은 이 문제는 숫자가 커지는 것에서 끝이 아닌 작아지는 것도 포함하여 최대 길이를 구하여야 된다.
• 이 문제의 핵심은 2차원 배열을 이용하여 2가지 종류의 최대 길이를 저장 해줄 것이다. 첫번째는 점점 커지는 경우에서 최대 길이를 기록 해주며 두번째는 점점 감소하는 경우에서 최대 길이를 배열에 저장한다. 그 다음 같은 인덱스에 있는 저장 된 두 값의 합 중 최대값에서 빼기 1 해준 값이 곧 최대길이가 된다.
  1. 우선, 첫번째 경우인 점점 커지는 경우는 #11053: 가장 긴 증가하는 부분 수열와 푸는 방식이 똑같다. 간단하게 설명하자면 배열을 한칸씩 바텀업 방식으로 확인하면서 이전 값들 중 자신보다 작은 값들 중 최대값에 더하기 1(자신)을 해준 뒤 배열에 기록해준다. 자세한 설명은 #11053: 가장 긴 증가하는 부분 수열을 확인하길 바란다.
  2. 두번째 경우는 점점 작아지는 경우인데 첫번째 경우와 완전 반대로 하면 된다. 우선, 제일 오른쪽에서 시작하여 왼쪽으로 가면서 모든 인덱스를 확인한다. 현재 인덱스에서 오른쪽에 있는 값들 중에 자신보다 작은 값이 있다는 것은 길이가 늘어날 수 있다는 것으로 그 중 최대 길이를 가진 값에 1을 더하여 배열에 길이를 저장해준다.
• 배열에 저장이 모두 끝난 뒤에는 두 값의 합 중에서 최대 크기를 answer값에 기록 해준 뒤 출력 시 자기 자신이 중복된 것을 빼기 위해 1을 빼준 뒤 출력해준다.

코드:

#include <iostream>
#define FORTH 0
#define BACK 1

using namespace std;

int main(){
	int n, answer = 0, arr[1000],dp[1000][2]={};
	//입력 
	cin >> n;
	//앞으로 가면서 커지는 값들의 최대 길이 기록 
	for(int i = 0; i < n; i++){
		int max_num = 0; //이전 최대값 0으로 초기화 
		cin >> arr[i];
		//이전 인덱스 방문 
		for(int j = 0; j < i; j++){
			//이전 인덱스 값 중 자신보다 작은 값 중에서 최대 길이 기록 
			if(arr[i] > arr[j])  max_num = max(max_num, dp[j][FORTH]);
		}
		//최대길이 + 자기자신(1) 더한 뒤 배열에 저장 
		dp[i][FORTH] = max_num+1; 
	}
	//뒤로 돌아가면서 커지는 값들의 최대 길이 기록
	for(int i = n-1; i >= 0; i--){
		int max_num = 0; //이전 최대값 0으로 초기화
		//현재 배열의 오른쪽에 있는 모든 인덱스 방문 
		for(int j = i; j < n; j++){
			//오른쪽 인덱스 중에 자신보다 작은 값 중 최대 길이 기록 
			if(arr[i] > arr[j]) max_num = max(max_num, dp[j][BACK]);
		}
		//최대길이 + 자기자신(1) 더한 뒤 배열에 저장 
		dp[i][BACK] = max_num+1;
		//앞으로 갔을 때의 최대 길이와 거꾸로 돌아왔을 때 최대 길이의 합 중 최대값 
		answer = max(answer, dp[i][FORTH]+dp[i][BACK]);
	}
	cout << answer-1; //자기 자신 중복 제외 
}