백준/DP
(c++)백준 11722번: 가장 긴 감소하는 부분 수열
Nimgnoej
2020. 6. 9. 16:48
https://www.acmicpc.net/problem/11722
11722번: 가장 긴 감소하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} �
www.acmicpc.net
2020/06/09 - [백준/DP] - (c++)백준 11053번: 가장 긴 증가하는 부분 수열
위 문제와 거의 똑같다. 부등호 하나만 바꿔주면 된다.
#include <iostream>
using namespace std;
int N;
int A[1001];
long long dp[1001];
void DP() {
long long Max = -1;
//모두 1로 초기화
for (int i = 1; i <= N; i++) {
dp[i] = 1;
}
for (int i = N - 1; i >= 1; i--) {
long long maxLength = 0;
for (int j = i + 1; j <= N; j++) {
//자신보다 더 작은 값 나타나면 그 값을 처음으로 했을 때
//가장 긴 부분 수열 길이를 더하기 (여러개면 부분 수열 길이가 가장 긴 것 더하기)
if (A[i] > A[j] && maxLength < dp[j]) {
maxLength = dp[j];
}
}
dp[i] += maxLength;
}
for (int i = 1; i <= N; i++) {
if (Max < dp[i])
Max = dp[i];
}
cout << Max << endl;
}
int main() {
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> A[i];
}
DP();
return 0;
}