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

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N, cnt = 1;
int A[1001];
int ans[1001];

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

	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> A[i];
	
	ans[1] = 1;

	for (int i = 2; i <= N; i++)
	{
		int tmp = 0;
		for (int j = 1; j < i; j++)
		{
			if (A[j] > A[i])
				tmp = max(tmp, ans[j]);
		}
		ans[i] = tmp + 1;
		cnt = max(cnt, ans[i]);
	}

	cout << cnt << '\n';
}

 

 

 

www.acmicpc.net/problem/11722

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