[백준 11722번] 가장 긴 감소하는 부분 수열 (C++)

문제링크 : https://www.acmicpc.net/problem/11722

 

#include <bits/stdc++.h> 
using namespace std;

int n;
int dp[1001];
int arr[1001];

int main()
{
	cin >> n;
	for (int i = 1; i <=n; i++)
	{
		cin >> arr[i];
		dp[i] = 1;              //가장 짧은 길이가 1이므로 1로 초기화
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j < i; j++)    
		{
			if (arr[i] < arr[j])      //arr[1 ~ i-1]까지 값 중에 arr[i]보다 큰 값이 있는지 확인
			{
				dp[i] = max(dp[i], dp[j] + 1);  //있다면 수열이 1칸 증가하므로 1을 더해줌
			}
		}
	}
	sort(dp, dp + 1001);
	cout << dp[1000];    //가장 긴 수열 길이 출력
}

조건에 맞을 때 해당 dp에 1씩 더해줌으로서 길이를 증가시켜준다.