백준 11722 가장 긴 감소하는 부분순열

백준(알고리즘)

백준 11722 가장 긴 감소하는 부분순열

빡상이 2020. 12. 26. 21:01

www.acmicpc.net/problem/11722

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

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}

www.acmicpc.net

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

int frontnum;
int main()
{
	int n;
	cin >> n;
	vector <int> arr;
	vector <int> brr(1001);
	int max = -999;
	int temp;
	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		arr.push_back(temp);
	}

	for (int i = 0; i < n; i++)
	{
		brr[i] = 1;
		for (int j = 0; j < i; j++)
		{
			if (arr[i] < arr[j] && brr[i] <= brr[j])
				brr[i] = brr[j] + 1;
		}
		if (max < brr[i])
			max = brr[i];
	}
	cout << max;
}

탐색을 통하여 그 뒤의값이 전의 값보다 작고 && brr에서 증가하는 경우에만 brr[i]값을 증가시켜 탐색하였다