[백준] C++ 11054번:가장 긴 바이토닉 부분 수열

 

풀이)

동적 계획법의 한 문제로

증가 부분의 수열과 감소부분의 수열을 나누어 값을 구한 뒤에 

두 값들의 합의 최댓값을 구하면 되는 문제입니다.

 

여기서 증가 부분의 수열을: ldp

감소 부분의 수열을 :rdp로 칭하였습니다.

 

코드는 다음과 같습니다.

 

코드)

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

int main()
{
	int n;
	cin >> n;

	array<int, 1001> arr;

	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
	}

	vector<int> ldp(n, 1);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			if (arr[i] > arr[j])
				ldp[i] = max(ldp[i], ldp[j] + 1);
		}
	}

	vector<int> rdp(n, 1);

	for (int i = n - 1; i >= 0; --i) {
		for (int j = n - 1; j > i; --j) {
			if (arr[i] > arr[j])
				rdp[i] = max(rdp[i], rdp[j] + 1);
		}
	}

	int cnt{};
	for (int i = 0; i < n; ++i) {
		cnt = max(cnt, ldp[i] + rdp[i] - 1);
	}

	cout << cnt;

}

 

결과)

 

개인적으로 동적계획법이 저한테는 어렵게 느껴지는 것 같습니다.

이렇게 간단한 코드임에도 이를 생각해내는 부분이 어려워 많이 연습해봐야겠습니다.