백준 11053번: 가장 긴 증가하는 부분 수열

[문제 링크]

11053번: 가장 긴 증가하는 부분 수열

---

알고스팟의 LIS 문제와 같은 문제였다. 

 

Top-down 방식의 알고리즘은 1~N번째에서 시작하여 아래 방향으로 1번째까지 탐색하면서 가장 긴 LIS를 찾아주도록 구현하였고, 기저사례로 현재 위치가 1번째일 경우 LIS는 반드시 1이므로 1을 반환하도록 하였다.

 

Bottom-up 방식의 알고리즘은 1번째에서 시작하여 윗 방향으로 1~N번째까지 탐색하면서 가장 긴 LIS를 찾아주도록 구현하였다. 1번째까지만 탐색하는 경우와 LIS가 최소일 때 길이는 무조건 1이므로 dp배열을 1로 초기화 해주었다.

---

#include <iostream>
using namespace std;

int arr[1001], memo[1001];

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

int TopDown(int here)
{
	if (here == 1) return 1;

	int& ret = memo[here];
	if (ret != 0) return ret;

	ret = 1;

	for (int i = here-1; i > 0; i--)
		if (arr[i] < arr[here])
			ret = max(ret, TopDown(i) + 1);

	return ret;
}

int BottomUp(int N)
{	
	for (int i = 0; i < 1001; i++)
		memo[i] = 1;

	int ret = 1;
	for (int i = 2; i <= N; i++)
	{
		for (int j = 1; j <= i; j++)
			if (arr[i] > arr[j] && memo[i] < memo[j] + 1)
				memo[i] = memo[j] + 1;

		ret = max(ret, memo[i]);
	}

	return ret;
}

int main(void)
{
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> arr[i];
	
	// Top-down
	int res = 0;
	for (int i = 1; i <= N; i++)
		res = max(res, TopDown(i));
	cout << "Top-down: " << res << endl;

	// Bottom-up
	cout << "Bottom-up: " << BottomUp(N) << endl;

	return 0;
}

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