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

문제출처 : https://www.acmicpc.net/problem/11722

1. 문제요약

- 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하라

- A = {10, 30, 10, 20, 20, 10}

  A = {10, 30, 10, 20, 20, 10} 가장 긴 감소하는 부분 수열의 최대 길이는 3

2. 접근방법

- LIS와 같음

3. 시간복잡도

- n^2

4. 회고

소스코드

#include<iostream>
using namespace std;

int n, d[1001], a[1001], ans = 0;

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < n; i++){
		d[i] = 1;
		for (int j = 0; j < i; j++)
			if (a[i] < a[j] && d[i] < d[j] + 1)
				d[i] = d[j] + 1;
		if (ans < d[i]) ans = d[i];
	}
	cout << ans << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]