백준 BOJ 2565 - 전깃줄

오버킬

https://www.acmicpc.net/problem/2565

2565번: 전깃줄

lis의 nlogn이 주제였으므로 의도치않게 오버킬을 했다.

 

입력받은 값을 pair에 넣고 정렬 후 lis구하기.

 

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

vector<int> v;
vector<pair<int,int>> input;

int main(){
	v.push_back(-INF);
	
	int n,a,b;
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%d %d", &a, &b);
		input.push_back({a,b});
	}
	
	sort(input.begin(), input.end());
	
	for(int i=0; i<n; i++){
		if(v[v.size()-1] < input[i].second){ v.push_back(input[i].second); }
		else{
			auto it = lower_bound(v.begin(), v.end(), input[i].second);
			*it = input[i].second;
		}
	}
	
	printf("%d", n-v.size()+1);
	return 0;
}