[백준 2565] 전깃줄

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

---

해설

이번 문제는 LIS 를 이용 해 풀었다.

푼 방법은 일단 A를 기준으로 정렬하고, A와 연결 된 B에 대해서 LIS를 때려주었다.

거기서 나온 LIS를 n에서 빼주어 답을 내었다.

 

 

˙˙˙

 

소스코드

 

#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;
int dp[1010];
int arr[101];
int main() {
	pair<int, int >vp[101];
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> vp[i].first >> vp[i].second;
	sort(vp, vp + n);
	int res = -1;
	for (int i = 0; i < n; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++)
			if (vp[j].second < vp[i].second)
				dp[i] = max(dp[i], dp[j] + 1);
		res = max(res, dp[i]);
	}
	cout << n- res << '\n';
}

 

오류 지적, 질문 환영합니다.