[백준] 알고리즘 11053번 - 전깃줄 문제

문제

www.acmicpc.net/problem/2565

2565번: 전깃줄

소스코드

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> v1;
int dp[501];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n,ans=0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x>> y;
		v1.push_back(make_pair(x, y));
	}
	sort(v1.begin(), v1.end());
	for (int i = 0; i < n; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if(v1[j].second<v1[i].second)
				dp[i] = max(dp[i], dp[j] + 1);
		}
		ans = max(dp[i], ans);
	}
	cout << n - ans;
}

풀이

LIS 문제를 해결하고 이 문제를 해결하면 쉽게 풀 수 있다.

DP[i]에는 i번째를 마지막으로 했을경우의 증가되는 수열의 길이를 저장한다.

이 문제에서는 제거되는 전깃줄과 가장긴 증가되는 수열의 길이의 관계를 생각해내면 풀 수 있다.