BOJ 2565 | 전깃줄

LIS 문제라는 것을 알고 풀었기 때문에 아이디어는 한 번에 보였고, 두 가지 방법으로 구현해서 풀었다.

첫 번째는 $O(N^2)$으로 구현했는데, 다음과 같은 코드로 작성했다.

int mxlength = 0;
	for (int i = 0; i < arr.size(); i++){
		dp[i] = 1;
		for (int j = 0; j < i; j++){
			if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + 1);
		}
		mxlength = max(mxlength, dp[i]);
	}

원리는 간단하다.
$dp[i]$는 $arr[i]$까지의 LIS 길이를 담게 하고, $dp[i+1]$을 구하기 위해 $dp[0]$ ~ $dp[i]$를 전부 탐색해서 조건에 맞는 가장 큰 $dp[x]$를 채용했다.

이 방법은 떠올리기도 쉽고, 간단하지만 사실 LIS는 $O(N log N)$으로 구하는 게 구현도 훨씬 간단해서 저걸 제대로 구현하기까지 조금 헤맸다.

뭔가 생각이 다른 데 가있었는지 자꾸 그리디로 구현하고 있어서 4% WA만 한 5번은 맞은 것 같다.

두 번째 방법은 $O(N log N)$으로 구현하는 방법이다.

vector<int> lis;
	for (auto &i: arr){
		if (lis.size() == 0 || lis.back() < i) 
        	lis.push_back(i);
		else 
        	lis[lower_bound(lis.begin(), lis.end(), i) - lis.begin()] = i;
	}

딱 보기에도 간단하게 생긴 이 방법이 LIS를 구현하는 웰노운 풀이법이다.
인터넷에 이 방법에 대한 해설은 차고 넘치므로 조금 특별하게 내가 이해한 것을 써보겠다.

arr 배열에 들어 있는 값이 10 2 8 1 11 3 5 6 이라고 해보겠다.

첫 번째 연산을 마치고 난 후, lis 배열에 들어가 있는 값이다.

$arr[1]$이 계산되면, lis 배열에 10 대신 2가 들어가게 된다.
작은 원은 대체된 숫자를 의미한다.

$arr[2]$가 계산되고 나면, lis 배열에 새로운 자리가 생기면서 8이 들어간다.

$arr[3]$이 계산된 후의 모습이다.
이 때가 중요하다.

LIS는 $[1, 8]$일 수 있을까? 그럴 수 없다.
원래 배열은 10 2 8 1 이므로 여기서 LIS는 $[2, 8]$이 된다. 그렇다면 왜 첫 번째 자리가 갱신되었는가?

그건 바로 lis 배열이 나타내는 것이 LIS가 아니라 LIS의 길이이기 때문이다.

아케이드 게임기에서 누가 990만점을 내서 HIGH SCORE을 갈아치웠다고 해보자.
800~850만점 사이를 내는 사람들 100명이 게임을 더 한다고 해서 HIGH SCORE가 사라지는가? 아니다.

다른 사람들이 그 게임기에 앉아서 게임을 해도, 990만점의 HIGH SCORE는 여전히 그 게임기 랭킹 1위에 자리잡고 있을 것이다.

만약 10 2 8 에서 갱신된 $[2, 8]$이 의미가 사라지려면, 완전히 새로운 길이가 3인 LIS가 등장해야 한다.
이 경우에만 이전 LIS가 의미를 잃게 되고, 이 규칙이 반드시 지켜져야 한다.

$arr[4]$가 계산된 모습이다.
별로 중요하지 않으니 넘어가자.

$arr[5]$까지 계산되어 10 2 8 1 11 3 까지 진행된 모습이다.
착각하지 말아야 하는 게, 현재 LIS는 $[2, 8, 11]$로 1과 3이 lis 배열에 자리잡고 있지만 이미 밀려난 숫자들이 진짜 LIS를 형성하고 있다.

그렇다면 언제까지 이 밀려난 친구들이 LIS를 유지하고 있을까?

아까 전에 밀려난 10을 한번 보자.
10은 현재 LIS에 포함되어 있지 않고, 추후 새로운 수가 들어오더라도 LIS에 포함될 가능성을 완전히 잃어버렸다.
언제 이런 일이 벌어졌을까?

먼저 2가 들어와서 10이 밀려난 상황을 생각했을 때, LIS는 $[2]$와 $[10]$으로 두 가지가 공존하고 있다.

그러나 이후 8이 들어오면서 LIS는 $[2, 8]$로 유일해졌다.
10 -> 8은 불가능하므로 10은 현재 LIS에서 벗어났다.
또한, 더 큰 수가 들어오더라도 10이 LIS에 포함되는 것은 불가능하다.
8보다 더 큰 수는 오른쪽에 추가되어 LIS의 길이를 늘려버릴 것인데, 10이 LIS에 포함되려면 lis[1]이 10보다 큰 수로 바뀌어야 하기 때문이다.

따라서 다음 칸에 [LIS 후보 수열의 마지막 수]보다 작은 수가 들어오게 된다면, 그 수열은 LIS의 가능성을 완전히 잃어버린 것이다.

원래 과정으로 돌아오자.

이제 $LIS$는 2개가 되었다. $[1, 3, 5]$와 $[2, 8, 11]$인데, 흥미로운 순간이다.
만약 11보다 더 큰 수가 들어오면 $LIS$는 계속 2개일 수 있지만 그렇지 않다면 $LIS$가 교체될 수 있다.

마지막 계산이 끝나고 완성된 lis 배열의 모습이다.

$[2, 8, 11]$은 완전히 가능성을 잃어버렸고, $[1, 3, 5, 6]$은 $LIS$가 되었다.
조심해야 할 점은, 위 예시처럼 lis 배열이 항상 $LIS$를 나타내는 것은 아니라는 것이다.

10 2 8 1 11 3 5 12 13 9 로 시도해보자.
아마 아래와 같은 모양이 나올 것이다.

$LIS$는 $[1, 3, 5, 12, 13]$ 과 $[2, 8, 11, 12, 13]$이지만, 모두 lis 배열은 아니다.
lis 배열은 $LIS$의 길이만을 나타낸다는 것에 주의하자.

코드

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

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

int board[501];
int dp[101];
vector<int> arr;

int main(){
	int N; cin >> N;
	for (int i = 0; i < N; i++){
		int t, v; cin >> t >> v;
		board[t] = v;
	}
	for (int i = 0; i < 501; i++){
		if (board[i]) arr.push_back(board[i]);
	}
	
	//for (auto &i: arr) debug << i << ' '; debug << endl;
	
	// LIS, O(N^2)
	/*
	int mxlength = 0;
	for (int i = 0; i < arr.size(); i++){
		dp[i] = 1;
		for (int j = 0; j < i; j++){
			if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + 1);
		}
		mxlength = max(mxlength, dp[i]);
	}*/
	
	//LIS O(NlogN)
	vector<int> lis;
	for (auto &i: arr){
		if (lis.size() == 0 || lis.back() < i) lis.push_back(i);
		else lis[lower_bound(lis.begin(), lis.end(), i) - lis.begin()] = i;
		
		//for (auto &j: lis) debug << j << ' ';
		//debug << endl;
	}
	
	cout << N - lis.size();
}