백준 - 꼬인 전깃줄 (1365) [C++]

이 문제는 LIS 문제 알고리즘을 이용해서 푸는 문제이다.

 

입력 값 최대가 10만이므로, O(n^2) 알고리즘 사용이 불가능하다. 따라서 O(N log N) 이하의 알고리즘을 찾아야 한다.

 

전깃줄이 꼬이지 않게 하는 최소의 제거 전깃줄 수를 구하는 문제는 다르게 말하면 전깃줄이 꼬이지 않는 최대의 전깃줄 수를 구하는 것과 같다. 즉, 이는 입력 배열에서 LIS를 찾고 이를 N과 빼주면 된다는 말과 같다.

 

LIS를 구하는 알고리즘 중 O(N log N) 시간을 요구하는 방법은 이분 탐색을 이용하는 방법이다. 해당 알고리즘을 통해 LIS를 구하고, 이를 N과 빼주면 정답이 나온다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX 100000

int N;
int arr[MAX];

void input() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
}

int lis() {
	vector<int> temp;
	temp.push_back(arr[0]);

	for (int i = 1; i < N; i++) {
		if (temp.back() < arr[i]) {
			temp.push_back(arr[i]);
		}
		else {
			int index = lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin();

			temp[index] = arr[i];
		}
	}

	return temp.size();
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	input();
	int result = lis();
	int answer = N - result;

	cout << answer << '\n';

	return 0;
}