백준_11722_가장 긴 감소하는 부분 수열

백준 11055번(가장 큰 증가 부분 수열) 과 유사한 다이나믹 프로그래밍(dp) 문제였다. i번까지의 수열의 최대 길이인 d[i]를 1로 초기화하고, 이전 값들과 모두 비교해서 갱신하는 방식으로 풀었다.

#include <iostream>
#include <algorithm>
#define MAX 1001

using namespace std;

int N, A[MAX], d[MAX], answer;

void dp() {
	int maxD = 0;
	for (int i = 1; i <= N; i++) {
		d[i] = 1;
		for (int j = 1; j < i; j++) {
			if (A[i] < A[j] && d[i] < d[j] + 1) {
				d[i] = d[j] + 1;
			}
		}
		maxD = max(maxD, d[i]);
	}
	answer = maxD;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
	}
	dp();
	cout << answer << '\n';
	return 0;
}