백준 2565번 - 전깃줄

www.acmicpc.net/problem/2565

2565번: 전깃줄

 

이 문제는 DP, 다이나믹 프로그래밍을 설명할 때 A반에서 출제했던 문제입니다. 이 문제를 처음 보면 어렵게 느껴질 수 있지만 그림을 그려서 따라가다 보면 쉽게 해결 할 수 있는 문제입니다.

 

풀이

1. 왼쪽 전봇대를 기준으로 오름차순으로 정렬을 시킵니다.

2. 오른쪽 전봇대에서 "가장 긴 증가하는 부분 수열"을 구해줍니다.

3. 2번 과정에서 구한 "가장 긴 증가하는 부분 수열"의 크기를 N에서 빼주면 답이 됩니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

vector <pair<int, int>> v;
int dp[105] = { 0, };

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	
	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		int a, b; cin >> a >> b; v.push_back(make_pair(a, b));
	}
	sort(v.begin(), v.end());

	dp[0] = 1;
	int ans = 0;
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (v[i].second > v[j].second)
				dp[i] = max(dp[i], dp[j] + 1);
			else
				dp[i] = max(1, dp[i]);
		}
		ans = max(dp[i], ans);
	}
	cout << N - ans;
}