백준 2565번: 전깃줄

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

2565번: 전깃줄

 

 

0. 알고리즘 분류

 다이나믹 프로그래밍

 

 

1. 문제

 

 

2. 풀이

 11053과 같은 LIS 문제이다. 처음 봤을 땐 이게 왜 LIS 문제인지 싶었는데, (구글링으로)무작위로 주어진 전깃줄 연결을 A 전봇대에서 오름차순으로 정렬하면, B 전봇대에서 값이 작아지면 줄이 꼬인다는 것을 의미한다. 즉, B 전봇대에서 가장 긴 증가하는 부분 수열을 구하고, N에서 이 값을 빼면 우리가 원하는 답이 나온다.

 

 문제를 풀 때 어려운 것은 역시, 어떤 알고리즘으로 푸는지 파악하는 것이다...

 

 

3. 코드

#include <bits/stdc++.h>

using namespace std;

int lis[101];

bool comp(vector<int> &a, vector<int> &b) {
	return a[0] < b[0];
}

int get_max(int a, int b) {
	return a > b ? a : b;
}

int binarySearch(int left, int right, int target) {
	int mid;
	
	while (left < right) {
		mid = (left + right) / 2;
		
		if (target > lis[mid]) {
			left = mid+1;
		}
		else {
			right = mid;
		}
	}
	
	return right;
}

int main(void) {
	int n;
	cin >> n;
	
	vector<vector<int>> arr(n);
	for (int i = 0; i < n; i++) {
		arr[i] = vector<int>(2);
		cin >> arr[i][0] >> arr[i][1];
	}
	
	sort(arr.begin(), arr.end(), comp);
	
	int ix = 0;
	lis[ix] = arr[0][1];
	
	for (int i = 1; i < n; i++) {
		if (lis[ix] < arr[i][1]) {
			lis[++ix] = arr[i][1];
		}
		else {
			int temp = binarySearch(0, ix, arr[i][1]);
			lis[temp] = arr[i][1];
		}
	}
	
	cout << n - ix - 1;
	
	return 0;
}