[백준] 1365 꼬인 전깃줄

백준 1365 꼬인 전깃줄

• https://www.acmicpc.net/problem/1365
• 길 왼쪽의 전봇대와 길 오른편의 전봇대를 연결하는 전선이 꼬여있지 않기 위해선, 오른편의 전봇대의 위치가 증가하는 수열이어야 한다.

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <vector>
using namespace std;

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

	int n;
	cin >> n;

	int lis = 0;
	vector <int> vt;
	vt.push_back(INT_MIN);

	for (int i = 0; i < n; i++) {
		int A;
		cin >> A;
		if (vt.back() < A) {
			vt.push_back(A);
			lis++;
		}
		else {
			auto it = lower_bound(vt.begin(), vt.end(), A);
			*it = A;
		}
	}

	cout << n - lis;
	return 0;
}