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

[문제 링크]

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

---

https://onlytrying.tistory.com/80 LIS와 같은 유형의 문제였다.

---

#include <iostream>
using namespace std;

int N, arr[1001], memo[1001];

int max(int a, int b) { return a > b ? a : b; }

int Topdown(int start)
{
	int& ret = memo[start];
	if (ret != 0) return ret;

	ret = 1;
	for (int i = start + 1; i <= N; i++)
		if (arr[start] > arr[i])
			ret = max(ret, Topdown(i) + 1);

	return ret;
}

int Bottomup()
{
	int res = 1;
	for (int i = 1; i <= N; i++)
	{
		memo[i] = 1;
		for (int j = 1; j < i; j++)
			if (arr[i] < arr[j])
				memo[i] = max(memo[i], memo[j] + 1);
		res = max(res, memo[i]);
	}

	return res;
}

int main(void)
{
	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> arr[i];
	
	int res = 1;
	for (int i = 1; i <= N; i++)
		res = max(res, Topdown(i));
	cout << res << endl;

	cout << Bottomup() << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 87 day