C++ / 2565 / 전깃줄 ( 다이나믹 프로그래밍 )

https://www.acmicpc.net/problem/2565

문제 요약

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였습니다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 합니다.

예를 들어, < 그림 1 >과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 됩니다.

 

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨집니다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성해야합니다.

 

문제 풀이

이 문제는 기존의 dp문제랑 또 다른 유형이었습니다.

 

LIS(최장 증가 부분 수열)을 구해야 하는 문제라 기존의 탑다운 방식으로는 풀 수 없는 문제였습니다.

지피티 썼다 이말입니다.

 

나중에 다시 풀어봐야할듯

 

1. 전깃줄을 pair로 입력받습니다.

2. 입력받은 전깃줄을 정렬해줍니다.

3. lis 계산을 합니다.

4. i번째 전깃줄을 마지막 전깃줄로 하였을때 교차하지 않으면 그 전깃줄의 기존 값( dp )을 더해주고 해당 전깃줄 까지 세어줍니다.

5. 증가시킨 개수 중에 최대값을 저장합니다.

6. 전체 전기줄에서 세어준 전기줄 개수를 빼서 출력합니다.

 

주의할 점

i 번째 선이 마지막에 들어올때 계산하는 것 입니다.

그래서 i와 교차되지 않을 경우에만 

코드

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

using namespace std;

int n;
int dp[104];
vector<pair<int, int>>v;
int main()
{
	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());

	// 전깃줄 담을 변수
	int lis = 0;
	for (int i = 0; i < n; i++)
	{
		dp[i] = 1;
		for (int j = 0; j < n; j++)
		{
			if (v[j].second < v[i].second)
			{
				// i번째 전깃줄과 교차하지 않으면 기존 전깃줄이 가지고 있던 개수를 더하고 해당 전기줄 까지 세어줍니다.
				dp[i] = max(dp[i],dp[j]+1);
			}
		}
		// 최대 전기줄 개수
		lis = max(dp[i], lis);
		
	}
	//전체 전기줄 - 최대 전기줄 개수
	cout << n-lis;
}

예제

8
1 8
3 9
2 2
4 1
6 4
10 10
9 7
7 6

결과