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

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

O(NlogN) LIS 알고리즘으로 풀어야 하는 문제이다.

 

arr 배열엔 입력 값을 저장한다.

 

tmp 배열의 인덱스는 수열의 길이를 나타내고

각 값은 현재 길이를 가진 수열의 마지막 원소 중

가장 작은 값의 위치를 저장한다.

 

dp 배열엔 각 인덱스가 연결하고 있는 인덱스를 저장한다.

 

변수 len엔 지금까지 가장 긴 수열의 길이를 저장한다.

 

계산이 모두 끝나면 tmp[len]이

LIS의 마지막 원소의 위치를 가리키고 있으므로

dp[tmp[len]] 부터 재귀 호출로

dp의 값이 -1이 될 때까지

(더 이상 연결돼 있는 원소가 없는 경우 -1이 저장되어 있음)

역추적 한 뒤 그때부터 출력하면서 차례로 빠져나온다.

 

이 영상을 보면 설명이 좀 불친절하지만 이해하는데 도움이 된다.

#include <iostream>
using namespace std;
int N, arr[1000001], tmp[1000002], dp[1000001], len = 1;

void Print(int idx) {
	if (dp[idx] == -1) {
		cout << arr[idx] << " ";
		return;
	}
	Print(dp[idx]);
	cout << arr[idx] << " ";
}

int lower_bound(int key, int start, int end) { // 찾으려는 key값이 없으면 key값 보다 큰 가장 작은 값 반환
	while (start < end) { // end가 start보다 같거나 작아지면 그 값이 lower bound이므로 종료
		int mid = (start + end) / 2;
		if (arr[tmp[mid]] >= key) end = mid; // 중간 값이 key보다 크거나 같으면 중간 값을 끝 값으로 다시 설정
		else start = mid + 1; // 중간 값이 key보다 작을 땐 중간 값+1을 시작 값으로 설정
	}
	return end;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		dp[i] = -1;
		if (arr[tmp[len]] < arr[i]) dp[i] = tmp[len], tmp[++len] = i; // 현재 LIS를 충족하면 dp[i]엔 LIS의 마지막 원소였던 값의 위치 저장, len은 +1, tmp[len]엔 현재 위치 저장
		else {
			int idx = lower_bound(arr[i], 1, len); // LIS를 충족하지 못 하면 이분 탐색으로 현재 위치를 저장할만한 위치 찾음
			tmp[idx] = i; // idx길이를 가진 수열 중 가장 작은 값의 위치가 저장됨
			if (idx != 1) dp[i] = tmp[idx - 1];
		}
	}
	cout << len << "\n";
	Print(tmp[len]);
	return 0;
}