[C/C++] 백준 14002번 - 가장 긴 증가하는 부분 수열 4 (LIS)

 

 

 

<시간복잡도 O(N²) 코드> 

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

int N, A[1001], len;
int index, tmp;
int dp[1001];
vector<int> v;

int main()
{
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> A[i];
		len = 0;

		for (int j = 1; j < i; j++)
		{
			if (A[j] < A[i])
				len = max(dp[j], len);
		}
		dp[i] = len + 1;
		
		// 최대 길이와 최대 값 저장
		if (tmp < len + 1)
		{
			tmp = len + 1; // 최대 길이
			index = i; // 최대 값의 인덱스
		}
	}

	for (int i = index; i >= 1; i--)
	{
		if (dp[i] == tmp)
		{
			v.push_back(A[i]);
			tmp--;
		}
	}

	int size = v.size();
	cout << size << '\n'; 
	for (int i = 0; i < size; i++)
	{
		cout << v.back() << " ";
		v.pop_back();
	}
}

 

<시간복잡도 O(NlngN) 코드>

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

int N, cnt;
int A[1000001], dp[1000001];
vector<int> v, ans;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> A[i];
		
	v.push_back(A[1]);

	for (int i = 2; i <= N; i++)
	{
		if (v[cnt] < A[i])
		{
			v.push_back(A[i]);
			cnt++;
			dp[i] = cnt;
		}
		else
		{
			int pos = lower_bound(v.begin(), v.end(), A[i]) - v.begin();
			v[pos] = A[i];
			dp[i] = pos;
		}
	}

	int LIS_size = cnt;

	for (int i = N; i >= 0; i--)
	{
		if (dp[i] == LIS_size)
		{
			ans.push_back(A[i]);
			LIS_size--;
		}
	}

	int size = ans.size();
	cout << size << '\n';
	for (int i = 0; i < size; i++)
	{
		cout << ans.back() << " ";
		ans.pop_back();
	}
	
}

 

 

 

풀이 방법

 

dp[i] : i번째까지 중에서 가장 긴 수열의 길이

index	1	2	3	4	5	6
A[ ]	10	20	10	30	20	50
dp[ ]	1	2	1	3	2	4

 

for (int i = 1; i <= N; i++)
{
	cin >> A[i];
	len = 0;
    
	for (int j = 1; j < i; j++)
	{
		if (A[j] < A[i])
          		len = max(dp[j], len);
	}
	dp[i] = len + 1;
		
	// 최대 길이와 최대 값 저장
	if (tmp < len + 1)
	{
		tmp = len + 1; // 최대 길이
		index = i; // 최대 값의 인덱스
	}
}

처음에 수열을 입력받으면서 dp를 채워주고 밑에 if구문은 수열의 최대 길이와 최대 값을 저장하게 됩니다.

이 반복문을 지나 tmp에는 수열의 최대 길이인 4,
index에는 수열 A중 가장 큰 값인 '50'의 인덱스 값 6이 저장됩니다.

 

for (int i = index; i >= 1; i--)
{
	if (dp[i] == tmp)
	{
		v.push_back(A[i]);
		tmp--;
	}
}

그리고 index부터 1 까지 거꾸로 탐색하면서

dp값이 4인 값 '50'을 벡터에 push,

dp값이 3인 값 '30'을 벡터에 push,

dp값이 2인 값 '20'을 벡터에 push,

dp값이 1인 값 '10'을 벡터에 push 해주게 됩니다.

 

int size = v.size();
cout << size << '\n'; 
for (int i = 0; i < size; i++)
{
	cout << v.back() << " ";
	v.pop_back();
}

그리고 벡터를 back에서 값을 꺼내면서 출력합니다.

 

 

www.acmicpc.net/problem/14002

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