백준 2565 전깃줄

 

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

 

서론

LIS 문제라는것을 알았는데도 풀이를 떠올리지 못했다.

전깃줄을 제거하는게 아니라 역으로 교차하지 않는 전깃줄을 세는것을 알고 난 후 문제의 예제 그림을 통해 이해할 수 있었다.

 

풀이

주어진 입력을 문제의 예제 그림과 같이 만들기 위해 A위치를 기준으로 오름차순 정렬한다.

그 후 B 위치를 기준으로 LIS정렬 해주면 된다.

 

구현

//c++

#include <iostream>
#include <algorithm>

using namespace std;

typedef struct {
	int first;
	int second;
}st;

int dp[102];
st line[102];

bool compare(st a, st b) {
	return a.first < b.first;
}

int main() {
	int n;
	int result = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> line[i].first >> line[i].second;
	}
	sort(line, line + n + 1, compare);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			if (line[i].second > line[j].second) {
				if (dp[j] >= dp[i]) { 
					dp[i] = dp[j] + 1;
				}
			}
		}
		result = max(result, dp[i]);
	}
	cout << n - result;
}