백준 11054 : 가장 긴 바이토닉 부분 수열 C++ 정답&해설

 

https://github.com/o920/baekjoon/blob/master/11054.cpp

o920/baekjoon

 

 

 

 

1. N 입력 받음

2. N개의 수열 입력 받음

3. 왼쪽에서부터 가장 긴 증가하는 수열 구하기

4. 오른쪽에서부터 가장 긴 증가하는 수열 구하기

5. 왼+오 합친 것 중 가장 큰 수 - 1을 해줌 (Sk가 두번 카운트 됐기 때문)

 

#include <iostream>
#include <algorithm>
using namespace std;
int N;
int num[1000];
int dp_left[1000], dp_right[1000];

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) cin >> num[i];
    
	// dp 배열 모두 1 로 초기화 해주기
	fill_n(dp_left, 1000, 1);
	fill_n(dp_right, 1000, 1);

	for (int i = 0; i < N; i++) {
		for (int j = i-1; j >= 0; j--) {
			if ((num[j] < num[i])&& (dp_left[i] < dp_left[j]+1)) dp_left[i] = dp_left[j] + 1;
		}
	}
	for (int i = N - 1; i >= 0; i--) {
		for (int j = i + 1; j < N; j++) {
			if ((num[j] < num[i]) && (dp_right[i] < dp_right[j]+1)) dp_right[i] = dp_right[j] + 1;
		}
	}
	int m = 0;
	for (int i = 0; i < N; i++) {
		m = max(m, (dp_left[i] + dp_right[i]));
	}
	cout << m - 1 << endl;

 

---