#include <bits/stdc++.h>
using namespace std;
int n, num, len = 0;
int nums[1005];
pair<int, int> tempMax; // 지금까지의 최대 stack,
int dp[1005];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j <= i; j++) {
if (nums[i] < nums[j] && dp[i] <= dp[j]) { //현재 숫자가 이전의 숫자보다 작다. &
dp[i] = dp[j] + 1;
}
}
}
int result = 1;
for (int i = 0; i < n; i++) {
result = max(dp[i], result);
}
cout << result;
}
이번 DP는 따로 점화식은 필요없이 떠오르는 대로 하면 풀릴 문제였다.
'백준 문제 풀이 & C++ 공부' 카테고리의 다른 글
백준 11049 C++ (0) | 2025.03.26 |
---|---|
백준 15468 C++ (0) | 2025.03.15 |
백준 11726 C++ (0) | 2025.03.05 |
백준 2579 C++ (0) | 2025.03.05 |
백준 2748 C++ (0) | 2025.03.04 |