백준 2565번 - 전깃줄

 

 

 

* 문제 링크

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

2565번: 전깃줄

 

 

 

 

 

 

문제 내용 요약

 

전봇대에 높이에 따라 1번부터 500번까지 있는데, 전깃줄은 두 전봇대 각각의 번호 한 쌍을 연결한다.

 

근데 이게 교차되면 합선되니까 교차가 안되게 제거할 전깃줄의 최소 개수를 구해라

 

 

 

 

 

 

 

접근법

 

단계별로 풀어보기에도 나와있지만, 이 문제 또한 LIS의 응용 문제다.

 

LIS에 관한 설명은 아래의 링크를 참고하자.

 

https://syerco0.com/22

백준 11053번 - 가장 긴 증가하는 부분 수열 (LIS)

 

 

 

일단은 이 문제가 왜 LIS를 이용하면 되는지부터 보도록 하겠다.

 

전깃줄이 교차하기 위한 조건은 무엇인가?

 

예시로 A전깃줄과 B전깃줄이 있을 때, 왼쪽 전봇대에 각각 1번, 2번 위치에 있다고 하자.

 

그러면 오른쪽 전봇대에 각각 어떤 위치에 있을 때 교차할까?

 

 

 

A전깃줄이 B전깃줄보다 더 큰 값의 위치에 있으면 교차한다.

 

왼쪽에서 증가할 때, 오른쪽에서 감소하는 형태면 교차한다.

 

그림을 대충 그렸지만 이해는 되었을 것이라 생각한다.

 

그렇다면 왼쪽에서도 증가, 오른쪽에서도 증가하는 식으로 연결될 경우, 교차하지 않을 것이다.

 

이게 최대로 되려면?

 

 

왼쪽 전봇대에서 값이 증가하는 방향으로 전깃줄을 놓았을 때,

 

오른쪽 전봇대에서 가장 큰 증가하는 부분 수열(LIS)을 구하면?

 

남길 수 있는 최대 전깃줄 개수를 구할 수 있다.

 

빨간 색이 남길 전깃줄, 파란 색이 없앨 전깃줄이다.

 

구해야될 것은 지워야할 최소 전깃줄 개수니까,

 

전체 개수에서 남길 최대 전깃줄 개수를 빼면 답을 구할 수 있다.

 

 

 

아 입력으로 주는 전깃줄이 정렬되어있는 상태가 아니기 때문에

 

정렬해주는 것을 잊지 말아야 한다.

 

 

 

 

내 코드

#include <iostream>
#include <algorithm>
using namespace std;
struct E{
	int x,y;
};
E e[105];
int m[105];
bool cmp(E a,E b) {
	return a.x<b.x;
}
int main() {
	int n,x=-1;
	cin>>n;
	for(int i=0;i<n;i++) scanf("%d %d",&e[i].x,&e[i].y);
	sort(e,e+n,cmp);
	for(int i=0;i<n;i++) {
		m[i]=1;
		for(int j=0;j<i;j++) if(e[j].y<e[i].y) m[i]=max(m[i],m[j]+1);
		x=max(x,m[i]);
	}
	cout<<n-x;
}