[백준] 2565번 전깃줄

1. Approach

 

(1) 다이나믹 프로그래밍으로 접근한다.

 

-> 전봇대 A와 연결되어 있는 전깃줄에 대해서 정렬하고 LIS를 수행한다.

 

(2) 풀이 방법

 

-> (1)번에서 설명한 방식대로 접근하면 쉽게 해결 가능하다.

 

2. Source Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<pair<int,int>> a;					// first : A
											// second : B
int dp[101];
int main()
{
	int x, y;			// x -> y
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x >> y;
		a.push_back(make_pair(x, y));
	}
    // 정렬 수행
	sort(a.begin(), a.end());
    // LIS 수행
	for (int i = 0; i < n; i++)
	{
		dp[i] = 1;
		for (int j = 0; j < i; j++)
		{
			if (a[j].second < a[i].second && dp[i] < dp[j] + 1)
			{
				dp[i] = dp[j] + 1;
			}
		}
	}
	cout << n - *max_element(dp + 1, dp + n + 1);
	return 0;
}

3. 비슷한 문제

1. 가장 긴 증가하는 부분 수열 -> www.acmicpc.net/problem/11053

4. 참조

---

www.acmicpc.net/problem/2565