[백준] 2565 전깃줄

백준2565

두 전봇대 사이의 전깃줄이 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 문제이다.
전깃줄이 교차하지 않으려면 연결된 번호가 순차적으로 증가하거나, 감소해야한다.
LIS(Longest Increasing Subsequence) 관련 문제인데

8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

라는 예제를 보자.
왼쪽 전봇대를 기준으로 오름차순 정렬하면

1 8
2 2
3 9
4 1
6 4
7 6
9 7
10 10

이 된다.

이제 오른쪽 전봇대에서 LIS를 구하면, 그 LIS의 길이는 교차하지 않고 남아있을 수 있는 최대 전깃줄의 개수가 되므로
전체 전깃줄에서 LIS의 길이를 빼면 제거해야 할 전깃줄의 개수가 나온다.

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

int main() {
	int N; //전깃줄의 개수, 100이하으 자연수
	vector<pair <int, int>> p;
	int a, b;
	vector<int> dp;

	cin >> N;
	dp = vector<int>(N, 1); //1로 초기화된 N개의 원소를 가지는 벡터 생성

	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		p.push_back({ a,b });
	}
	sort(p.begin(), p.end());

	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= i; j++) {
			if (p[j].second < p[i].second && dp[i] < dp[j] + 1)
				dp[i]++;
		}
	}

	printf("%d", N - (*max_element(dp.begin(), dp.end())));
	return 0;
}