[백준] 2565번 : 전깃줄

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, LIS 문제를 응용하여 푸는 문제이다.

1) n에 전깃줄의 개수를 입력받아 저장한다.

2) edges 벡터를 선언하고, n개 만큼의 전깃줄에 대해 pair(A 전봇대 번호, B 전봇대 번호)를 입력받아 저장한다. 그리고 A 전봇대 번호를 기준으로 edges를 오름차순 정렬한다.

3) A 전봇대 번호의 오름차순으로 A 전봇대와 연결된 B 전봇대의 번호들을 정렬하면 하나의 수열이 만들어진다. 겹치는 전깃줄이 없으려면 (모든 A 전봇대 번호에 연결된 B 전봇대 번호)는 (더 큰 A 전봇대 번호와 연결된 B 전봇대 번호)보다 작아야 한다.

• ex. (A 전봇대 1 - B 전봇대 5) 와 (A 전봇대 2 - B 전봇대 4) 가 있으면 서로 겹치게 됨.

4) 따라서 만들어진 수열에서 최장 증가 수열을 구하면
-> 가장 많은 전깃줄 개수를 유지함과 동시에 전깃줄이 겹치지 않는 경우이다.

5) 최장 증가 수열(LIS) 구하기

• dp[i] : 수열이 i 번째 인덱스까지 있을 때, i 번째 수를 포함하는 최장 증가 수열의 길이
• i 번째 인덱스의 수와 j(0 ~ i-1) 번째 수를 차례대로 비교하며 dp를 갱신한다.
  • 만약 (i 번째 수 > j 번째 수) and (dp[j] + 1 > dp[i]) 라면
    • dp[i]를 dp[j] + 1로 갱신한다.
    • maxCount < dp[i]면 maxCount를 dp[i]로 갱신한다.
      (maxCount = 현재까지 최장 증가 수열 길이)

6) 전체 수열 길이 n에서 maxCount를 빼면 필요 없는 전깃줄 == 제거해야하는 전깃줄의 개수가 나온다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;

int n;
vector<pii> edges;	// 전선의 시작 번호, 끝 번호 저장
int dp[101];

int solution()
{
	int maxCount = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j < i; j++)
		{
			if (edges[j].second < edges[i].second && dp[j] + 1 > dp[i])
			{
				dp[i] = dp[j] + 1;

				if (maxCount < dp[i])
					maxCount = dp[i];
			}
		}
	}
	return n - maxCount;
}

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

	cin >> n;
	edges.push_back(pii(0, 0));
	for (int i = 1; i <= n; i++)
	{
		int a, b;
		cin >> a >> b;
		edges.push_back(pii(a, b));
		dp[i] = 1;
	}
	sort(edges.begin(), edges.end());
	cout << solution();
}