가장 긴 증가하는 부분 (feat. 백준, 11053번)

가장 긴 증가하는 부분
https://www.acmicpc.net/problem/11053

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

반응형

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

1. 저는 뒤의 값을 기준으로 비교를 했습니다.
2. 가령 5 1 2 1 3 4 라는 값이 있다고 하면, 5 1 을 비교 / 5 2, 1 2 를 비교 / 5 1, 1 1, 2 1 을 비교 / 5 3, 1 3, 2 3, 1 3 을 비교 / 5 4, 1 4, 2 4, 1 4, 3 4 를 비교 하는 순서입니다.