[boj 1365] 꼬인 전깃줄

 

icpc.me/1365

1365번: 꼬인 전깃줄

아이디어는 다음과 같은 조건에서 얻을 수 있다

꼬인 전깃줄을 최소로 풀어서 꼬여있는 쌍이 없도록 한다

이것이 문제에서 요구하는 것인데

 

x,y(x>y)에서 각각 a,b로 가는 전깃줄이 있다면

b가 a보다 큰 경우에 전깃줄이 있다는 것이 자명하다

그렇다면 a[i] = j일때 i에서 j로 전깃줄이 연결되어 있다 생각하면

LIS를 구하는 문제가 아닐까?라고 떠올릴 수 있다

 

코드

#include <bits/stdc++.h>

int n;
int arr[100000 + 5]; //a[i] = j라면 i와 j를 전깃줄로 연결한것
vector<int> v;

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
    
	v.push_back(-1e9);
	for (int i = 0; i < n; i++) {
		if (v.back() < arr[i]) v.push_back(arr[i]);
		else {
			auto it = lower_bound(v.begin(), v.end(), arr[i]);
			*it = arr[i];
		}
	}
	cout << n - v.size() + 1 << endl;

	return 0;
}