[C++]BOJ 11053 - 가장 긴 증가하는 부분 수열

이전의 반도체 설계 문제와 동일하게 최장 증가 수열을 구하는 문제다.

2020년 4원 7일 포스트 수정

저 문제 풀 때는 dp가 뭔지도 몰랐다.
이번엔 동적 계획법으로 풀어봤다.
dp[i]에 arr[i]이전의 값들을 비교하며 arr[i]보다 작은 값이 있다면 그 때의 dp[]에 담겨있는 값 + 1을 dp[i]에 넣는다. arr[i]이전의 모든 수에 위 과정을 반복했을 때 가장 큰 수가 dp[i]가 된다.
마지막으로 dp[]에 담겨있는 값 중 가장 큰 값이 최장증가수열의 길이가 된다.

#include <iostream>
#include <algorithm>
using namespace std;
int n, arr[1001], dp[1001];
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> arr[i];
		dp[i] = 1;
		for(int j = i; j != 0; j--)
			if(arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + 1);
	}
	sort(dp, dp + n + 1);
	cout << dp[n];
}