가장 긴 감소하는 부분 수열 (feat. 백준, 11722번)

가장 긴 감소하는 부분 수열
https://www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/11722
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	register int N, arr[1001], dp[1001];
	cin >> N;
	for (register int i = 1; i <= N; ++i)
		cin >> arr[i], dp[i] = 1;
	for (register int i = 1, j; i <= N; ++i)
		for (j = 1; j <= i; ++j)
			if (arr[j] > arr[i])
				dp[i] = max(dp[i], dp[j] + 1);
	cout << *max_element(dp + 1, dp + 1 + N) << endl;
	return 0;
}
// *&)*@*

기본적으로 dp를 사용하는 방법에 대해서 잘 알수 있는 문제입니다.

아래는 같이 보시면 더욱 좋은 문제들입니다.

문제들의 해답도 블로그에 올려둔 상태입니다.

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

 

 

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