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

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

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

lis nlogn구현과 함께 역추적이 가능한지를 묻는 문제였다

 

일단 처음으로 문제에 접근했던 방법은

각 자리 lis배열의 최솟값을 저장하는건데 이건 WA가 나왔었고,

 

반례를 접하고 나서의 접근은

일단 lis의 그 끝 값을 구성하는 수가 나온 뒤에

이보다 작은 값이 나올때 순서대로 채워나가는 것이었다.

즉 for문을 통해 역순회하면서 정답 배열또한 역순으로 채워주면 된다.

 

#include <bits/stdc++.h>
#define INF 1234567890
using namespace std;

vector<int> lis;
vector<int> v;
pair<int,int> back[1234567];
int ans[1234567] = {0};

int main(){
	for(int i=0; i<1234567; i++) ans[i] = INF;
	lis.push_back(-INF);
	
	int n,k;
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%d", &k);
		v.push_back(k);
	}
	
	for(int i=0; i<n; i++){
		if(lis.back() < v[i]){
			lis.push_back(v[i]);
			back[i] = {v[i], lis.size()-1};
		}
		else{
			auto it = lower_bound(lis.begin(), lis.end(), v[i]);
			*it = v[i];
			int tmp = distance(lis.begin(), it);
			back[i] = {v[i], tmp};
		}
	}
	
	printf("%d\n", lis.size()-1);
	
	int ptr = lis.size()-1;
	for(int i=n-1; i>=0; i--){
		if(back[i].second == ptr){
			ans[ptr] = back[i].first;
			ptr--;
		}
	}
	for(int i=1; i<=lis.size()-1; i++){ printf("%d ", ans[i]); }
	return 0;
}

자력으로 푼 플래 >_<