11054) 가장 긴 바이토닉 부분 수열 c++

문제 ) www.acmicpc.net/problem/11054

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

 

풀이 ) 

가장 긴 바이토닉 부분 수열은 앞에서부터 차례대로 증가 수열을 찾고, 뒤에서부터 차례대로 증가 수열을 찾은 뒤,

앞에서 부터의 증가수열 값과 뒤에서 부터의 증가수열 값을 더한 뒤 겹치는 인텍스인 1을 빼주면 된다.

1. dp 배열을 이중 배열로 설정했다.
   dp[0][1001] = 앞에서부터 찾은 증가 수열
   dp[1][1001] = 뒤에서부터 찾은 증가 수열

2. 반복문을 돌면서 현재 인텍스 배열값인 A[i] 와 그 이전의 값들을 비교하면서 A[i] 가 이전 값들보다 크면 1씩 증가해주면 된다.

 

코드 )

#include <iostream>
#include <algorithm>
using namespace std;

int N, sum;
int A[1001];
int dp[2][1001];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for(int i=0; i<N; i++)
		cin >> A[i];
	
    	// 앞에서부터 증가 수열 확인
	for(int i=0; i<N; i++) {
		dp[0][i] = 1;
		
		for(int j=0; j<i; j++) {
			if( A[i] > A[j] )
				dp[0][i] = max(dp[0][i], dp[0][j]+1);
		}
	}
	
    	// 뒤에서부터 증가 수열 확인
	for(int i=N-1; i>=0; i--) {
		dp[1][i] = 1;
		
		for(int j=N-1; j>=i; j--) {
			if( A[i] > A[j] )
				dp[1][i] = max(dp[1][i], dp[1][j]+1);
		}
	}
    
	// 가장 긴 바이토닉 부분 수열의 길이를 구하기
	for(int i=0; i<N; i++) {
		if( sum < (dp[0][i] + dp[1][i]-1))
			sum = dp[0][i] + dp[1][i] -1;
	}
	
	cout << sum;
}