[백준]14003번 가장 긴 증가하는 부분 수열 5 - C/C++

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

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

문제

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

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

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.

---

 N = 1000000 이기 때문에 lower_bound를 활용한 O(NlogN)의 LIS 알고리즘을 활용해야 한다.

dp [] 에는 LIS의 길이를 구하기 위한 값을 가지고 있고 실제 LIS를 구성하는 원소를 가지고 있지는 않기 때문에

memo[] 에 이 원소가 몇 번째 LIS 원소로 선정되었는지 저장해둔 다음 역추적하여 배열을 출력할 수가 있다.

{ 8 14 9 17 2 15 16 } 배열의 경우 LIS는 { 8 9 15 16 }이지만  dp의 값은 {2 9 15 16}으로 실제 LIS와 다르다.

그러므로 memo[] 를 활용하여 배열의 끝에서부터 역추적하여 답을 구해낼 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#define MAX 1000010

using namespace std;

int N;
int arr[MAX],dp[MAX],memo[MAX];
stack <int> ans;
int len = 0;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	dp[len++] = arr[0];
	memo[0] = 0;
	for (int i = 1; i < N; i++) {
		if (arr[i] > dp[len - 1]) {
			dp[len++] = arr[i];
			memo[i] = len - 1;
		}
		else {
			int* iter = lower_bound(dp, dp + len, arr[i]);
			*iter = arr[i];
			memo[i] = iter - dp;
		}
	}
	cout << len << "\n";
	int cnt = len - 1;
	for (int i = N - 1; i >= 0; i--) {
		if (cnt == memo[i]) {
			ans.push(arr[i]);
			cnt--;
		}
	}
	while (!ans.empty()) {
		cout << ans.top() << " ";
		ans.pop();
	}
	return 0;	
}

---

LIS 여서 무작정 DP로 풀다가 시간 초과에 걸렸다. 저번 포스팅에서 시간 복잡도를 계산하고 풀자고 다짐했건만 지켜지지 못했다. 하지만 고민했어도 이 풀이를 생각해내기에는 굉장히 힘들었을 것 같다! 구글링을 하다 보니 과거의 내가 다른 백준 LIS 문제를 lower_bound를 이용하여 푼 기록이 있던데 아마 그냥 구글에서 베껴 내지 않았을까 싶다. lower_bound를 쓴 기억이 없는데 이번에는 꼭 기억해야겠다!