[DP] 11722번 가장 긴 감소하는 부분 수열

https://www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

- 문제 파악

수열이 주어지고, 수열 중 일부를 선택하여 감소하는 부분 수열을 만들 수 있는 경우 중에서 수열의 길이가 가장 긴 값을 출력하라.

 

- 정답

가장 긴 증가하는 부분 수열 감소 버전이다.

 

기준이 되는 수열을 하나 지정하고(i), 0부터 i-1까지 배열들 중에서 자신보다 작은 수열들이 존재하면, 자신 보다 작은 수열이 가질 수 있는 최대 길이와 나 자신을 더한 것과 현재 i가 가질 수 있는 최대 길이를 비교한다.

 

#include "bits/stdc++.h"

using namespace std;

int n;
int D[1001];
int arr[1001];
int ans = 1;


int main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	for (int i = 0; i < n; i++)
	{
		D[i] = 1;
		for (int j = 0; j < i; j++)
		{
			if (arr[i] >= arr[j])
				continue;

			D[i] = max(D[j] + 1, D[i]);
		}

		ans = max(D[i], ans);
		
	}

	cout << ans;

}