백준 2656 전깃줄

문제를 있는 그대로 받아들여서 교차점이 제일 많은 전깃줄부터 제거하여 문제를 풀려 했지만 교차점이 같은 전깃줄에서 어느 것을 먼제 제거할지 결정하기가 어려웠다..

결국 서치하여 알아낸 것은

문제 풀이 방법이 증가하는 가장 긴 부분 수열을 구하는 문제라는 것!

 

 

왼쪽 전봇대와 오른쪽 전봇대를 볼 때, 왼쪽에서 출발하는 전깃줄이 도착하는 오른쪽 전봇대의 인덱스를 나열하여, 그중에서 제일 긴 증가하는 부분수열을 구하면 되는 문제였다..

 

가장 긴 증가하는 부분 수열을 구하는 방법은?

dp 배열을 이용한다.

dp[a]=b의 의미는 a번째 값이 가지는 가장 긴 증가하는 부분 수열의 길이는 b이다. 라는 의미임

 

 

정렬되지 않은 순서로 입력이 주어질 수 있으므로 저장한 값을 먼저 정렬해주고, dp 배열에 값을 할당한다. 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int, int>>line;
vector<int>dp(501);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int from, to;
		cin >> from >> to;
		line.push_back(make_pair(from, to));
	}

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


	int answer = 1;
	for (int i = 0; i < n; i++) {
		dp[i] = 1;
	}
	for (int i = 1; i < n; i++) {
		for (int j = i-1; j >=0; j--) {
			if (line[j].second < line[i].second) {
				dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
			}
		}
		answer = dp[i] > answer ? dp[i] : answer;
	}

	cout << n - answer;

	return 0;
}