[백준 문제풀이 / C++] 2565 전깃줄

 

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

2565번: 전깃줄

 

 

알고보면 간단하지만, 한번 꼬아진 문제이기 때문에 해결하기 쉽지 않았다.

 

LIS 알고리즘 ( Longest Increasing Subsequence - 최장증가수열알고리즘) 관련된 문제로,

 

이를 한번 꼬아서 낸게 특징이다.

 

전깃줄이 겹치는 것을 어떻게 구현할지 고민했었는데,

 

A 전봇대의 point를 기준으로 정렬하고, B전봇대의 point를 LIS 알고리즘 통해 크기를 비교하여 겹치지않는 점들을 구할 수 있다(증가수열).

 

 

즉, 문제해결 전략은

 

서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수 = n개의 줄 - 최장증가수열을 이루는 전깃줄들 수

 

이고 해결 코드 및 주석은 아래와 같다.

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<pair<int, int> > v;
int cnt[101] = { 0, };
int ans;

int main(){
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		v.push_back(make_pair(a, b));
	}
	// A 전봇대의 점을 토대로 정렬하게 된다.
	sort(v.begin(), v.end());
	ans = 1;

	for (int i = 0; i < n; i++){
		cnt[i] = 1;
		for (int j = 0; j < i; j++){
			// 이미 A전봇대의 점을 토대로 정렬이 되어있기때문에, B전봇대의점을 비교하게 되는데
			// v[j].second 가 v[i].second 보다 작게되면 v[i]와 v[j]는 겹치지않는 전선 (증가수열)이 된다.
			// 이렇게 최장증가수열을 만든다.
			if (cnt[j] + 1 > cnt[i] && v[j].second < v[i].second) cnt[i] = cnt[j] + 1;
		}
		if (ans < cnt[i])ans = cnt[i];
	}
	// 최장증가수열을 만들어, n개의 점에서 그 갯수를 빼주면 필요없는 전선의 최소갯수가 나온다.
	printf("%d\n", n-ans);
	

	return 0;
}

 

 

추가적으로 LIS 알고리즘 관련하여 풀어보면 좋을 문제는 아래와 같다.

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

11053번: 가장 긴 증가하는 부분 수열

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

11055번: 가장 큰 증가 부분 수열