[BAEKJOON] 11054번 가장 긴 바이토닉 부분 수열

문 제

 

소 스  코 드

#include <iostream>
#include <algorithm>

int main() {
	int N;
	std::cin >> N;

	int *seq{ new int[N] };
	int *l_dp{ new int[N] };
	int *r_dp{ new int[N] };
	
	for (int i = 0; i < N; ++i) std::cin >> seq[i];

	std::fill_n(l_dp, N, 1);
	std::fill_n(r_dp, N, 1);
	
	int max_length{ -1 };
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < i; ++j) 
			if (seq[i] > seq[j]) l_dp[i] = std::max(l_dp[i], l_dp[j] + 1);
	}

	for (int i = N - 1; i >= 0; --i) {
		for (int j = N - 1; j > i; --j) {
			if (seq[i] > seq[j]) r_dp[i] = std::max(r_dp[i], r_dp[j] + 1);
		}
	}

	for (int i = 0; i < N; ++i) max_length = std::max(max_length, l_dp[i] + r_dp[i] - 1);


	std::cout << max_length;

	delete[] seq;
	delete[] l_dp;
	delete[] r_dp;
	return 0;
}

 

풀 이

11053번 가장 긴 증가하는 부분 수열

• 위의 가장 긴 증가하는 부분 수열과 같은 방식으로 풀면 구현이 가능하지만 주의해야 할 점은 어느 한 숫자를 기점으로 왼쪽과 오른쪽으로 갈 수록 숫자가 작아져야 하는 문제점을 가지고 있다. 

• 이때, 왼쪽에서 한 숫자를 가는 기점은 dp를 통한 구현을 통하여 간단하게 구현 할 수 있지만, 한 숫자를 기점으로 하여 오른쪽으로 이동할 경우 숫자가 작아져야 하는 부분에 대하여 고민을 하여, 한 번더 역순으로 구하여 두 dp간의 합에 공통된 부분 1을 제외 하여 구현 하였습니다.

 

결 과 값

 

 

문 제  출 처

문제 링크 : [ BAEKJOON ] : https://www.acmicpc.net/problem/11054