[백준] 2656번 전깃줄

2565번: 전깃줄

왼쪽 전봇대 번호를 기준으로 오름차순 정렬한 후 LIS를 구하고 총 전깃줄 개수에서 LIS를 빼주었다.

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

int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> line(n);
	for (int i = 0; i < n; i++) {
		int from, to;
		cin >> from >> to;
		line[i] = make_pair(from, to);
	}
	sort(line.begin(), line.end());
	vector<int> dp(n);
	dp[0] = 1;
	for (int i = 1; i < n; i++) {
		int maxLength = 0;
		for (int j = 0; j < i; j++) {
			if (line[i].second > line[j].second && dp[j] > maxLength)
				maxLength = dp[j];
		}
		dp[i] = maxLength + 1;
	}
	int lis = 0;
	for (int i = 0; i < n; i++) {
		if (dp[i] > lis) lis = dp[i];
	}
	cout << n - lis;
	return 0;
}