백준 1965번: 상자넣기

[문제 링크]

1965번: 상자넣기

---

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)
{
	if (start == n) return 1;

	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];

	// top-down
	int res = 1;
	for (int i = 1; i <= n; i++)
		res = max(res, Topdown(i));
	cout << res << endl;

	// bottom-up
	cout << Bottomup() << endl;

	return 0;
}

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