백준 2565번 전깃줄

- 문제 설명

 

두 전봇대 A와 B의 전깃줄이 임의로 연결되어 있을 때, 서로 겹치지 않도록 전깃줄들을 배치할 때 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램 작성

 

 

- 입력

 

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. (전깃줄의 개수는 100 이하의 자연수)

둘째 줄에는 한 줄에 하나 씩 A전봇대와 B전봇대가 연결되는 위치의 번호가 주어진다. (위치의 번호는 500 이하의 자연수, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.)

 

 

- 출력

 

모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수

 

 

* 문제 풀이의 핵심

 

0. 알고리즘 : LIS 알고리즘

 

모든 전깃줄이 연결된 상태에서 없애는 것이 아니라, 어떤 전깃줄을 선택하면 서로 교차하지 않고 가장 많이 연결할 수 있는지에 대해서 접근하면 된다.

 

1. 가능한 풀이방법은 2가지이다.

 

1) DP, 2중 for문 O(N²) = 100*100 (C++기준, 1초 : 10⁸ 이하)

2) 이분 탐색

 

※ 우선, 시작 위치의 전깃줄을 기준으로 오름차순 정렬한다.

 

2. DP

 

DP 배열을 만들어 특정 시점에 A, B가 연결되었을 때 얼마나 최대로 교차하지 않고 연결가능한지 저장

(dp[i][j] -> i : A 전깃줄 위치, j : B 전깃줄 위치)

 

1) dp의 값이 0 이라면, i 일 때 dp의 값을 1로 만들어 준다. (dp의 값은 0으로 초기화)i 번째 부터 전깃줄을 확장시켜 나가는 것이므로 처음 숫자는 1이다.

 

if (dp[line[i].start][line[i].end] == 0) {
	dp[line[i].start][line[i].end] = 1;
}

 

2) 순회하면서 DP의 값을 변경

- i 의 값은 항상 j 보다 커야한다.

- 위의 조건이 만족할 때, 최대로 전깃줄을 연결할 수 있는 개수가 늘어난다면 갱신

 

※ answer 값은 교차되지 않고 전깃줄을 최대로 연결할 수 있는 개수

 

for (j = 0; j < i; j++) {
  if (line[i].end > line[j].end) {
    if (dp[line[i].start][line[i].end] < dp[line[j].start][line[j].end] + 1) {
      dp[line[i].start][line[i].end] = dp[line[j].start][line[j].end] + 1;

      if (dp[line[i].start][line[i].end] > answer) {
      	answer = dp[line[i].start][line[i].end];
      }
    }
  }
}

 

2) 코드 순회 그림

 

 

- 소스코드

 

#include<iostream>
#include<algorithm>

using namespace std;

typedef struct LINE {
	int start;
	int end;
} LINE;

int num;
LINE line[101];
int dp[501][501] = { 0 };
int answer = -1;

bool cmp(LINE a, LINE b) {
	return a.start < b.start;
}

int main() {
	cin >> num;

	int i, j;
	for (i = 0; i < num; i++) {
		int s, e;
		cin >> s >> e;
		line[i].start = s;
		line[i].end = e;
	}

	sort(line, line + num, cmp);

	for (i = 0; i < num; i++) {
		if (dp[line[i].start][line[i].end] == 0) {
			dp[line[i].start][line[i].end] = 1;
		}
		
		for (j = 0; j < i; j++) {
			if (line[i].end > line[j].end) {
				if (dp[line[i].start][line[i].end] < dp[line[j].start][line[j].end] + 1) {
					dp[line[i].start][line[i].end] = dp[line[j].start][line[j].end] + 1;

					if (dp[line[i].start][line[i].end] > answer) {
						answer = dp[line[i].start][line[i].end];
					}
				}
			}
		}
	}

	cout << num - answer << "\n";
}

 

 

3. 이분탐색

 

- 로직

 

1) LIS의 값을 저장할 벡터 생성 후, 전깃줄의 첫 번째 값 삽입

 

2-1) 벡터의 끝 값 < 전깃줄의 값 : 벡터에 전깃줄의 값 삽입

 

2-2) 벡터의 끝 값 >= 전깃줄의 값 : lower_bound (작은 값과 근접) 이분탐색을 통해서 해당 값이 벡터의 어떤 위치에 들어갈 수 있는지 검색 후, 벡터의 값 갱신

 

3) 정답 : 전깃줄의 길이 - 교차하지 않고 최대로 연결할 수 있는 전깃줄의 길이 (벡터의 길이)

 

 

- 소스코드

 

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

typedef struct LINE {
	int start;
	int end;
} LINE;

int num;
LINE line[101];
vector<int> lis;
int answer = -1;

bool cmp(LINE a, LINE b) {
	return a.start < b.start;
}

int find_lower_bound(int n) {
	int left = 0;
	int right = lis.size() - 1;

	while (left < right) {
		int mid = (left + right) / 2;
		if (lis[mid] >= n) {
			right = mid;
		}
		else {
			left = mid + 1;
		}
	}

	return left;
}

int main() {
	cin >> num;

	int i, j;
	for (i = 0; i < num; i++) {
		int s, e;
		cin >> s >> e;
		line[i].start = s;
		line[i].end = e;
	}

	sort(line, line + num, cmp);

	lis.push_back(line[0].end);
	int l_idx = 0;
	for (i = 1; i < num; i++) {
		if (lis[l_idx] < line[i].end) {
			lis.push_back(line[i].end);
			l_idx += 1;
		}
		else {
			int idx = find_lower_bound(line[i].end);
			lis[idx] = line[i].end;
		}
	}

	cout << num - lis.size() << "\n";
}

 

 

- 문제링크 : https://www.acmicpc.net/problem/2565

2565번: 전깃줄

 

 

- 제출한 코드

 

DP

이분탐색

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요