BOJ 2565: 전깃줄

BOJ 2565: 전깃줄

두 전봇대에 전깃줄이 와장창 걸려있을 때, 이 전깃줄들이 최대한 겹치지 않도록 전선들을 잘 제거하는 문제이다.

문제 내용 전문

입력

첫째 줄에 전깃줄의 개수 (N)을 입력받고, 그 이후 N개의 줄 동안 전깃줄들이 연결되는 전봇대의 위치의 번호가 주어진다.

출력

모든 전깃줄이 교차하지 않도록 하기 위하여 없애야 하는 전깃줄의 최소 갯수를 출력한다.

N개의 전깃줄을 입력받았다고 생각해보자. 우리는 전선이 합선되지 않도록, 최소한의 전선을 제거하여야 한다.

최소한의 전선을 제거한다는 것은, 최대한 많은 전선들이 서로 겹치지 않고 배치되어 있다는 말과 같다. 그러므로, 우리는 LIS를 이용할 수 있다. 최대한 많은 전선을 겹치지 않게 배치한다는 것은, 전선들의 위치에 대하여 최장 증가 부분수열의 크기를 구한다는 것과 같은 의미이기 때문이다. 전체 전깃줄의 개수에서 LIS의 크기를 빼면, 우리가 원하는 답을 알아낼 수 있다.

기준으로 삼기 위하여 두 전봇대 중 한 전봇대를 기준으로 삼아 정렬한다. 그 후, 다른 전봇대에 대하여 LIS의 크기를 구하면 된다.

포인트
1. 입력받은 전깃줄의 위치들 ((X,Y) 형태)를 정렬하면, X에 대하여 오름차순으로 정렬된다.
2. 정렬한 것과 다른 좌표 (Y)에 대하여 LIS의 크기를 구한다.

작성한 코드는 다음과 같다.

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;

vector< pair<int, int> > arr;
int dp[105];
int n;
int m;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		arr.push_back({ x,y });
	}

	sort(arr.begin(), arr.end());

	for (int i = 0; i < n; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (arr[j].Y < arr[i].Y)
				dp[i] = max(dp[i], dp[j] + 1);
		}
		m = max(m, dp[i]);
	}

	cout << n - m;

	return 0;
}