알고스팟 _ LIS, 백준 12015번 _가장 긴 증가하는 부분 수열 2

2020-05-08 · 배운 것 · 5분 읽기

https://www.algospot.com/judge/problem/read/LIS

algospot.com ::
LIS

O(n^2) 풀이

반복문 풀이

#include <iostream>
#include <algorithm>

using namespace std;
int N;
int dp[501];
int arr[501];

void Input()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
}

void solve()
{
	int maxValue = 1;

	for (int i = 0; i < N; i++)
	{
		int value = arr[i];
		dp[i] = 1;
		for (int j = i; j >= 0; j--)
		{
			if (value > arr[j])
				dp[i] = max(dp[i], dp[j] + 1);
		}
		maxValue = max(maxValue, dp[i]);
	}
	cout << maxValue << '\n';
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int testcase;
	cin >> testcase;
	for (int i = 0; i < testcase; i++)
	{
		Input();
		solve();
	}
	return 0;
}

재귀방식 풀이

#include <iostream>
#include <algorithm>

using namespace std;
int N;
int dp[501];
int arr[501];

void dpInit()
{
	for (int i = 0; i < N; i++)
		dp[i] = -1;
}

void Input()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
}

int solve(int start)
{
	int& ret = dp[start];
	if (ret != -1)	return ret;

	ret = 1;
	for (int next = start + 1; next < N; next++)
		if(arr[start] < arr[next])
			ret = max(ret, solve(next) + 1);
	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int testcase;
	cin >> testcase;
	for (int i = 0; i < testcase; i++)
	{
		Input();
		dpInit();
		int maxValue = 0;
		for (int j = 0; j < N; j++)
			maxValue = max(maxValue, solve(j));
		cout << maxValue << '\n';
	}
	return 0;
}

O(nlogn) 풀이

이 문제는 백준 문제임.
https://www.acmicpc.net/problem/12015

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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n; // 벡터의 길이
vector <int> arr_a;

int main()
{
	cin >> n;
	arr_a.push_back(0);
	int tmp = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> tmp;
		if (arr_a.back() < tmp)
		{
			arr_a.push_back(tmp);
		}
		else
		{
			int index = lower_bound(arr_a.begin(), arr_a.end(), tmp) - arr_a.begin();
			arr_a[index] = tmp;
		}
	}

	cout << arr_a.size() - 1;

	return 0;
}

후기