백준 2565 전깃줄 (C++)

2565번: 전깃줄

dp 응용 문제이다. 전깃줄이 교차하지 않게 하기 위해 없애야 하는 최소 개수를 구해야한다. 교차하지 않는 다는 것은 주어진 input을 왼쪽 값을 기준으로 정렬했을 때 오른쪽 값이 전보다 커야한다는 것을 의미한다. 즉 왼쪽을 정렬한 상태에서 오른쪽 값들의 최대 증가 수열 수를 구해 전체 전깃줄 수에서 빼주면 된다. 반복문을 이용해 각 전깃줄에서의 최대 증가 수열 수를 구해 dp에 저장해주고 가장 긴 수를 res에 저장해 주었다.
푸는데 시간이 오래 걸린 문제였다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, res = 0;
vector<pair<int, int>> v;
int dp[100];

void solution() {
	sort(v.begin(), v.end());
	
	for (int i = 0; i < n; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (v[j].second < v[i].second) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}

		res = max(res, dp[i]);
	}

	cout << n - res;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;

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

	solution();
	
	return 0;
}