백준 14003 - 가장 긴 증가하는 부분 수열 5

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

https://www.acmicpc.net/problem/14003

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 LIS를 구하는 것이다.

 

일반적인 dp를 이용한 LIS는 $O(N^2)$이기 때문에 시간 초과가 발생할 것이다.

lower_bound를 사용하는 방법을 이용하면  $O(NlogN)$까지 줄일 수 있다.

하지만 이 방법을 해당 문제에서 그대로 적용할 수 없다.

왜냐하면 해당 방법은 배열을 뒤로 진행시키며 자신이 들어갈 위치의 값을 갱신하기 때문이다.

이를 해결하는 방법은 dp에 기록된 자리를 거꾸로 따라가면 된다.

 

예를 들어 보자.

for (int i = 0; i < N; i++)
{
    int pos = lower_bound(L.begin(), L.begin() + len, nums[i]) - L.begin();
    dp[i] = pos;

    if (pos + 1 > len) len++;
    L[pos] = nums[i];
}

이 코드가 lower_bound를 사용하는 전형적인 방법이다.

이렇게 하면 dp에 i번째 숫자까지의 LIS값이 기록된다.

이제 이를 거꾸로 타고가면 가장 긴 LIS를 구할 수 있다.

int LIS = len - 1;

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

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N;
vector<int> nums;
vector<int> dp;
vector<int> L;
vector<int> ans;
int len;
const int MAX = 1'000'000'001;


int main()
{
	INPUT_OPTIMIZE;

	cin >> N;
	nums.resize(N);
	dp.resize(N, 0);
	L.resize(N, MAX);

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

	for (int i = 0; i < N; i++)
	{
		int pos = lower_bound(L.begin(), L.begin() + len, nums[i]) - L.begin();
		dp[i] = pos;

		if (pos + 1 > len) len++;
		L[pos] = nums[i];
	}

	int LIS = len - 1;

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

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

	return 0;
}

---