[백준 C++] 2565 전깃줄 - 다이나믹프로그래밍

2565번: 전깃줄

---

 

문제풀이

 

다이나믹 프로그래밍을 이용해서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제입니다.

 

오름차순으로 나열한 A의 번호에 각각 연결된 B의 번호들을 순서대로 나열한 것을 하나의 수열로 생각하고

해당 수열에서 가장 긴 증가하는 부분 수열을 만들었을 때,

이 부분 수열에 해당하지 않는 숫자의 개수가 제거해야 하는 전깃줄의 최소 개수와 같습니다.

 

문제의 예제를 살펴보면,

A	1	2	3	4	6	7	9	10
B	(8)	2	(9)	(1)	4	6	7	10

 

B의 최장 증가 부분 수열을 구해보면 { 2, 4, 6, 7, 10 }이 되고

세 개의 전깃줄(1-8, 3-9, 4-1)을 제거하는 것이 최소값임을 알 수 있습니다.

---

코드

#include <iostream>
using namespace std;

int A[501];
int DP[501];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int N, LastB;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		int Ai, Bi;
		cin >> Ai >> Bi;
		A[Ai] = Bi;
		LastB = max(LastB, Bi);
	}

	int Max = 0;
	for (int i = 1; i <= 500; ++i)
	{
		if (A[i] == 0)
		{
			continue;
		}

		for (int j = 1; j < i; ++j)
		{
			if (A[j] == 0)
			{
				continue;
			}

			if (A[j] < A[i] && DP[j] > DP[i])
			{
				DP[i] = DP[j];
			}
		}

		++DP[i];
		Max = max(Max, DP[i]);
	}

	cout << N - Max;
}