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

 

 

 

문제 보러가기 : https://www.acmicpc.net/problem/11054

 

 

 

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

 

 

 

이번 문제는 다이나믹 프로그래밍 문제였습니다.

 

11053번 가장 긴 증가하는 부분 수열 문제와 유사하지만 이번 문제는 감소하는 부분 수열도 찾아줘야 했습니다.

 

 

 

《문제 풀이》

 

1. 가장 긴 증가하는 부분 수열의 길이를 기록할 배열 incre 와 가장 긴 감소하는 부분 수열의 길이를 기록할 배열 decre

2. incre 배열에서 자기 자신의 증가하는 부분 수열의 길이는 1이므로 모두 1로 초기화 

3. 가장 긴 바이토닉 부분 수열 찾기

     (1) 가장 긴 증가하는 부분 수열 찾기 (11053번 문제와 동일) 

        --> 두번째 값부터 현재 값으로 놓고, 0번째 값부터 현재 값 - 1 까지 비교하며 현재 값이 더 클 경우 갱신 

     (2) 가장 긴 감소하는 부분 수열 찾기 (거꾸로 생각하면 이것도 증가하는 부분 수열임)

        --> (N-2)번째 값부터 현재 값으로 놓고, (N-1)번째 값부터 현재 값 + 1 까지 비교하며 현재 값이 더 클 경우 갱신 

4. incre 배열과 decre 배열의 해당 인덱스에서의 최대합 출력

 

 

 

 

《C++ 코드》

 

#include <bits/stdc++.h>
#define MAX 1000

using namespace std;

int N;
int arr[MAX];
int incre[MAX];
int decre[MAX];

void bitonic() {
	
	// 가장 긴 증가하는 부분 수열 
	for(int i=1; i<N; i++) {
		int curVal = arr[i];
		
		for(int j=0; j<i; j++) {
			if(arr[j] < curVal) 
				incre[i] = max(incre[i], incre[j] + 1);
		}
	}
	
	// 가장 긴 감소하는 부분 수열  
	for(int i=N-2; i>=0; i--) {
		int curVal = arr[i];
		
		for(int j=N-1; j>i; j--) {
			if(arr[j] < curVal)
				decre[i] = max(decre[i], decre[j] + 1);
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin>>N;
	
	for(int i=0; i<N; i++)
		cin>>arr[i];
		
	// 자기 자신의 증가하는 부분 수열 길이는 1  
	fill_n(incre, N, 1);
	bitonic(); 
		
	int result = 0;
	for(int i=0; i<N; i++) {
		result = max(result, incre[i] + decre[i]);
	}
	cout<<result;
	return 0;
}

 

 

개발 환경: Dev-C++

 

 

baekjoon - 정답 화면