dp를 활용한 문제이다. 반복문을 돌면서 수열을 차례로 접근하면서 현재 위치를 기준으로 그 이전의 값들 중 작은 값을 찾아 카운트하여 dp
에 저장하였다. 그 중 가장 큰 dp
값을 구해 출력해주었다.
이전에 풀었던 가장 긴 바이토닉 부분 수열과 같은 유형 문제라서 쉽게 풀 수 있었다.
#include <iostream>
#include <algorithm>
using namespace std;
int N, res = 0;
int A[1000];
int dp[1000];
void solution(){
for (int i = 0; i < N; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (A[j] < A[i] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
res = max(res, dp[i]);
}
cout << res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> A[i];
}
solution();
return 0;
}