[BOJ] 2565 : 전깃줄 - travelbeeee

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

---

[ 알고리즘풀이 ]

 전깃줄의 상태가 들어오면 한쪽을 기준으로 sorting 한 후, 다른 쪽에서 LIS를 구하면 정답을 얻어낼 수 있습니다.

 

예시)

Sorting 전		Sorting 후
1	8	1	8
3	9	2	2
2	2	3	9
4	1	4	1
6	4	6	4
10	10	7	6
9	7	9	7
7	6	10	10

 왼쪽 전봇대를 기준으로 Sorting을 해보겠습니다.

 그 후, 왼쪽 전봇대는 Sorting이 되었으므로, 오른쪽 전봇대에서 가장 긴 증가하는 부분 수열을 찾는다면 그 부분 수열은 왼쪽 전봇대는 이미 Sorting 되어 있고, 오른쪽 전봇대에서도 증가하고 있으므로 서로 엉키지 않습니다! 즉, 서로 최대한 교차하지 않는 상태가 됩니다. 따라서, 가장 긴 증가 부분 수열의 길이를 구하고 N에서 빼준다면 제거해야 되는 전깃줄의 최소 개수를 얻어낼 수 있습니다.

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

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, a, b, dp[100] = {};
	vector<pair<int, int>> v;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		v.push_back(make_pair(a, b));
	}
	sort(v.begin(), v.end());
	// LIS구하는부분
	dp[0] = 1;
	for (int i = 1; i < N; i++) {
		int m = 0;
		for (int j = 0; j < i; j++)
			if (v[j].second < v[i].second)
				m = max(m, dp[j]);
		dp[i] = m + 1;
	}
	int m = 0;
	for (int i = 0; i < N; i++)
		m = max(dp[i], m);
	cout << N - m;
}

---