백준2565 - 전깃줄

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

2565번: 전깃줄

LIS문제다. 벡터의 인자로 pair를 받은 뒤 A 가로등을 기준으로 오름차순 정렬을 한다. 정렬이 된 상태에서 B에 LIS를 실행하여 최대 증가 수열을 찾으면 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	int n;
	int a, b;
	vector<pair<int, int>> v; //first는 A 전봇대, second는 B 전봇대
	vector<int> ans; //최대 증가 수열
	
	ans.push_back(0); //처음 기준으로 양수 밖에 없는 B 전봇대를 삽입하기 위해 0을 넣음

	//A 전봇대와 B 전봇대의 위치를 삽입
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		v.push_back(pair<int, int>(a, b));
	}

	//오름차순 정렬
	sort(v.begin(), v.end());

	//LIS를 실행
	for (int i = 0; i < v.size(); i++) {
		if (ans.back() < v[i].second) {
			ans.emplace_back(v[i].second);
		}
		else {
			auto it = lower_bound(ans.begin(), ans.end(), v[i].second);
			*it = v[i].second;
		}
	}

	//ans에서 0은 원소로 생각하면 안되니까 -1을 한다.
	cout << v.size() - (ans.size() - 1);
}