[백준 / BOJ] 2565번: 전깃줄

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

2565번: 전깃줄

 

 

---

 

코드

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

	int n, a, b, res = 0, dp[101];
	cin >> n;

	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		v.emplace_back(a, b);
	}
	sort(v.begin(), v.end());

	fill_n(dp, n, 1);
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i; j++)
			if (v[i].second > v[j].second && dp[i] < dp[j] + 1) dp[i] = dp[j] + 1;
		res = max(res, dp[i]);
	}

	cout << n - res;
	return 0;
}

 

 

 

---

 

 

DP 문제를 풀고 있고, 도저히 문제를 풀기 위한 아이디어가 생각나지 않아서 결국 다른 사람들의 풀이 방법을 보고왔는데 너무 간단한 아이디어라서.. 앞으로 새로운 유형이 나오면 잘 풀 수 있어야 할텐데 하는 걱정이 들었다.. 코테준비를 한지 얼마 안돼서 모르는게 많다고 위로중..!

 

풀이 아이디어는 다음과 같다.

 

왼쪽은 전깃줄 제거 전, 오른쪽은 최소 갯수의 전깃줄을 제거한 후의 그림이다.

이 그림을 잘 살펴보자.

왼쪽 그림을 살펴보면, B 전봇대에서 전깃줄이 연결된 번호를 A 전봇대 번호에 오름차순으로 정렬하여 나열하면 다음과 같다.

8  2  9  1  4  6  7  10

전깃줄을 제거한 오른쪽 그림도 같은 방법으로 나열하면 다음과 같다.

2  4  6  7  10 

즉, 전깃줄이 교차하지 않도록 최소 갯수를 제거하려면 증가하는 부분 수열의 최대 길이를 구하는 아이디어와 같은 방법을 사용할 수 있음을 알 수 있다(연결가능한 전깃줄의 최대 길이를 구한 후 전체 전깃줄 수에서 빼줌).

어떤 수열에서 증가하는 부분 수열의 최대 길이를 구하는 방법은 문제 11053번과 아이디어가 같다.

간단히 요약하면, 수열의 첫번째 수부터 i번째 수까지, 숫자 i를 포함하는 증가하는 부분 수열의 최대 길이를 구하기 위해서는 1~i-1번째 수들 중 i번째 수보다 작은 값을 찾고, 이 값들 중 증가하는 부분 수열의 길이가 최대인 값을 찾아 1을 더해주는 방식이다.