[백준] 2565 - 전깃줄

1. 문제 요약

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

두 전봇대 A와 B 사이에 여러 개의 전깃줄이 연결되어 있다.

각 전깃줄은 (A 위치, B 위치) 형태로 연결되어 있고 전깃줄이 서로 교차하면 합선 위험이 있기 때문에 일부 전깃줄을 제거하려고 한다.

목표는

전깃줄이 서로 교차하지 않도록 만들기 위해 제거해야 하는 전깃줄의 최소 개수를 구하는 것.

---

2. 처음 접근했던 방식

처음에는 전봇대 A의 위치를 기준으로 배열을 만들고 각 위치에서 조건을 검사하면서 교차 여부를 판단하려고 했다.

예를 들면 이런 식이었다.

graph = [0] * 501

graph[a] = b

 

그리고 단순히  if graph[i] >= i 같은 조건으로 교차 여부를 판단하려고 했다.

하지만 이 접근은 문제의 핵심을 놓치고 있었다.

왜냐하면 전깃줄의 교차는 하나의 전깃줄만 보고 판단할 수 없기 때문이다.

예를 들어 두 전깃줄이 있을 때

(A1, B1)
(A2, B2)

 

만약

A1 < A2
B1 > B2

 

이면 두 전깃줄은 서로 교차한다.

즉 전깃줄 간의 상대적인 순서가 중요하다.

---

3. 핵심 아이디어

이 문제의 핵심은 다음과 같다.

 1)A 전봇대 기준으로 전깃줄을 정렬한다.
 2) 그러면 A는 항상 증가하는 상태가 된다.
 3) 이제 B가 증가하는 순서로만 전깃줄을 선택하면 교차가 발생하지 않는다.

즉

B 배열에서 최장 증가 부분 수열(LIS)을 구하면 된다.

---

4. 왜 LIS가 되는가

예를 들어 A 기준 정렬 후 B 값이 다음과 같다고 하자.

8 2 9 1 4 6 7 10

 

여기서 증가하는 부분 수열만 선택하면 된다.

예를 들어

2 4 6 7 10

 

이 경우 B 값이 증가하므로 전깃줄은 서로 교차하지 않는다.

반대로

8 -> 2

 

처럼 감소하면 교차가 발생한다.

따라서

교차하지 않게 유지할 수 있는 최대 전깃줄 수 = LIS 길이

---

5. 우리가 구해야 하는 값

문제는 제거해야 하는 최소 개수를 묻는다.

따라서

제거해야 하는 전깃줄 수
= 전체 전깃줄 수 - LIS 길이

 

---

6. DP 풀이

DP 정의

dp[i] = i번째 전깃줄을 마지막으로 하는 LIS 길이

 

점화식

if B[j] < B[i]:
	dp[i] = max(dp[i], dp[j] + 1)

---

최종 코드

 

import sys
input = sys.stdin.readline

n = int(input())
lines = []

for _ in range(n):
a, b = map(int, input().split())
lines.append((a, b))

# A 기준 정렬
lines.sort()

dp = [1] * n

for i in range(n):
	for j in range(i):
		if lines[j][1] < lines[i][1]:
			dp[i] = max(dp[i], dp[j] + 1)

print(n - max(dp))

시간복잡도는

O(N^2)

 

이고 문제 조건에서 N ≤ 100이라 충분히 통과한다.