[C++] 백준 2565번 : 전깃줄

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

2565번: 전깃줄

---

문제 풀이

 전깃줄이 교차하지 않으려면 선들이 평행을 이뤄야 한다.

전깃줄의 각 꼭짓점은 위에서 아래로 내림차순을 이루고 있어서 LIS를 접목시키면 쉽게 풀 수 있다.

전깃줄을 이루는 각 꼭짓점의 숫자들이 LIS를 이룬다면 교차하지 않는 전깃줄들이 최대가 된다.

한쪽이 정렬되어있을 때 반대쪽의 LIS를 따지면 해결된다.

정렬은 STL에서 제공하는 sort 함수로 정렬하고 반대쪽 전봇대(B)의 값들의 LIS를 구하면 된다.

제거해야 할 전깃줄의 수를 구하면 돼서 총 전깃줄 개수에서 LIS의 길이를 빼주면 된다.

느낀 점

 LIS 문제를 풀고 나서 도전한 문제이기에 매우 쉽게 느껴졌다.

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, ans = 0;
int DP[101];
vector<pair<int, int>> arr;
pair<int, int> num;

int main() {
	cin >> n;
	for (int i = 0; i < n;i++) {
		cin >> num.first >> num.second;
		arr.push_back(num);
	}
	sort(arr.begin(), arr.end());
	for (int i = 0; i < n; i++) {
		DP[i] = 1;
		for (int j = 0; j < i;j++) {
			if (arr[i].second > arr[j].second && DP[i] < DP[j] + 1) {
				DP[i] = DP[j] + 1;
			}
		}
		ans = max(ans, DP[i]);
	}
	cout << n - ans;
}