[C++] 백준 2565번 전깃줄

LIS와 다이나믹 프로그래밍을 이용해서 풀었습니다.

전깃줄이 교차하지 않도록 만들때 최소한 끊어야하는 개수를 구하는 문제입니다.

양쪽 모두 숫자가 순차적으로 연결되어있다면 교차할 수 없습니다.
이를 통해 왼쪽을 기준으로 오른쪽이 최대한 순차적으로 되어있는 경우를 구했습니다.
그리고 전체 개수에서 가장 길게 순차적으로 되어있는 수를 빼면 제거해야할 전깃줄이 나옵니다.

먼저 왼쪽줄에 대한 정렬을 해주기 위해서 2차원 벡터를 사용했습니다.
sort를 통해서 왼쪽 기준으로 정렬을 해주었고
LIS를 통해서 가장 긴 늘어나는 수열을 구했습니다. 이 과정에서 DP를 사용했습니다.
vector의 사이즈 - DP의 가장큰 값을 빼주어서 문제를 풀었습니다.

 

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

int main(int argc, char *argv[])
{
	int n;
	int maxNum = -987654321;
	vector<vector<int>> line;
	vector<int> arr;
	vector<int> DP;

	cin >> n;

	for (int i = 0; i < n; ++i) {
		vector<int> v;
		int a, b;
		cin >> a >> b;
		v.push_back(a);
		v.push_back(b);
		line.push_back(v);
	}

	sort(line.begin(), line.end());
	
	for (int i = 0; i < n; ++i) {
		DP.push_back(1);
		arr.push_back(line[i][1]);
	}
	
	DP[0] = 1;
	for(int i = 1; i < n; ++i) {
		for (int j = i; j >= 0; --j) {
			if (arr[i] > arr[j] && DP[i] <= DP[j]) {
				DP[i] = DP[j] + 1;
			}
		}
	}

	for (int i = 0; i < n; ++i) {
		maxNum = max(maxNum, DP[i]);
	}


	cout << DP.size() - maxNum << endl;

	return 0;
}