2565번 전깃줄

문제링크 : www.acmicpc.net/problem/2565

2565번: 전깃줄

---

---

<알고리즘>

 1) 전깃줄의 양쪽 포인트를 입력받고, A 전봇대의 point를 기준으로 정렬한다.(오름차순)

 2) 이렇게 정렬했을 때, 전깃줄 간의 교차가 없으려면 B전봇대의 point들은 A전봇대처럼 순차적으로 커져야 한다.

 3) LIS 알고리즘을 이용하여 자신포함, 자신 앞에 순차적으로 된 전기줄의 숫자를 세어 dq에 기록

 4) 전체 전깃줄 수 - dq의 최댓값(전깃줄이 교차없이 이어진 최대의 경우의 수) 를 출력(=제거해야하는 전깃줄 수)

 

 

 

예제를 표로 보는 풀이

A	1	2	3	4	6	7	9	10
B	8	2	9	1	4	6	7	10
dq	1	1	2	1	2	3	4	5
	(1,8)	(2,2)	(2,2)(3,9)	(4,1)	(2,2)(6,4)	(2,2)(6,4)(7,6)	(2,2)(6,4)(7,6)(9,7)	(2,2)(6,4)(7,6)(9,7)(10,10)

 

 

 

메모리 : 2020KB    시간 : 0ms

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

int main() {
	int T = 0;
	cin >> T;

	vector<vector<int>> point(T,vector<int>(2));
	int A = 0;	int B = 0;
	for (int i = 0; i < T; i++) {
		cin >> A >> B;
		point[i][0] = A;
		point[i][1] = B;
	}
	sort(point.begin(), point.end());
		
	// 이 벡터로 세는 값은 i번 포인트 앞에 올바르게
	// 있는 선들의 개수이다.(자신포함)
	vector<int> dq(T, 1);
	int maximum = 0;
	for (int i = 0; i < T; i++) {
		for (int j = 0; j < i; j++) {
			if (point[i][1] > point[j][1]) {
				dq[i] = max(dq[i], dq[j] + 1);
			}
		}
		maximum = ((dq[i] > maximum) ? dq[i] : maximum);
	}
	cout << T - maximum << "\n";
	return 0;
}