백준 14003번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
3초	512MB	플래티넘 5

사진을 클릭하면 문제로 이동합니다.

---

풀이

 밀린 문제는 아니고 오늘 푼 문제이다. 문제 이름이 LIS니까 이 문제도 LIS이다. 다만, LIS를 역추적하는 문제이다.

 

 2568번 문제를 설명하는 이전 글에서 간략하게 설명했고, 알만한 사람들은 알겠지만, LIS알고리즘은 LIS 자체를 구하는 것이 아닌 LIS의 길이를 구하는 알고리즘이다. 그렇기 때문에 dp 배열을 하나 더 선언하여, 해당 dp 테이블을 역순회하면서 LIS를 다시 찾아가는 방식을 사용한다.

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;

int n;
vector<int> arr;

void input() {
	cin >> n;
	arr.resize(n);
	for(int& x : arr) cin >> x;
}

void sol() {
	vector<int> lis{-1000000001}, dp(n, 0);

	for(int i = 0; i < n; i++) {
		if(lis[lis.size() - 1] < arr[i]) {
			lis.push_back(arr[i]);
			dp[i] = lis.size() - 1;
		}
		else {
			int idx = lower_bound(ALL(lis), arr[i]) - lis.begin();
			lis[idx] = arr[i];
			dp[i] = idx;
		}
	}
	
	int len = lis.size() - 1;
	cout << len << endl;

	lis.resize(len);
	for(int i = n - 1; i >= 0 && len; i--) {
		if (dp[i] == len) {
			lis[--len] = arr[i];
		}
	}

	for(int l : lis) cout << l << ' ';
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	input();
	sol();
}