#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, mx;
cin >> n;
int arr[n];
int dp[n];
for (int i = 0; i < n; i++)
dp[i] = 1;
for (int i = 0; i < n; i++)
cin >> arr[i];
for (int i = 1; i < n; i++)
for (int j = i - 1; j >= 0; j--)
if (arr[i] > arr[j])
dp[i] = max(dp[i], dp[j] + 1);
mx = dp[0];
for (int i = 0; i < n; i++)
mx = max(mx, dp[i]);
cout << mx;
return (0);
}
#include <iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, mx;
cin >> n;
int arr[n];
int dp[n];
for (int i = 0; i < n; i++)
dp[i] = 1;
for (int i = 0; i < n; i++)
cin >> arr[i];
for (int i = n - 2; i >= 0; i--)
for (int j = i + 1; j < n; j++)
if (arr[i] > arr[j])
dp[i] = max(dp[i], dp[j] + 1);
mx = dp[0];
for (int i = 0; i < n; i++)
mx = max(mx, dp[i]);
cout << mx;
return (0);
}
점화식을 찾는 과정이 의외로 까다로웠습니다.
문제의 입력값의 범위가 1,000개로 시간복잡도 n^2을 사용해도 괜찮다는 판단으로
가장 기본적인 DP스타일로 이전값에 + 1 하는 식으로 문제를 해결했습니다.