[백준] 2565. 전깃줄 - Python

[Gold V]

 

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

2565번: 전깃줄

 

풀이

전깃줄이 교차하는 경우를 생각해 보자.

A 전봇대에서 B 전봇대로의 모든 전깃줄을 시작부터 숫자가 작은 순서대로 하나하나 연결한다고 생각할 때,

도착하는 위치가 이미 존재하는 도착지들보다 더 작은 숫자라면, 전깃줄이 교차하게 된다.

따라서 그러한 전깃줄들을 제거하면 되는 문제이다.

 

이 과정에서, A 전봇대에서의 출발 위치를 기준으로 정렬하게 되면, 아래와 같다.

[[1, 8], [2, 2], [3, 9], [4, 1], [6, 4], [7, 6], [9, 7], [10, 10]]

그리고 B 전봇대의 도착 위치만을 빼놓고 보면, 아래와 같다.

[8, 2, 9, 1, 4, 6, 7, 10]

이 배열에서의 최장 증가 수열 (LIS)를 구해, 그 길이를 원래 길이에서 빼면, 제거할 전깃줄의 개수를 구할 수 있다.

따라서, 이 문제는 LIS로 풀 수 있다.

 

보통 LIS는 Time Complexity 문제 때문에, Binary Search로 해결하는 경우가 더 많지만,

이 문제의 경우 n < 100 이기 때문에, DP로 풀이할 수 있다.

그러나 이 글에서는 Binary Search로 풀이한다.

 

import bisect
N = int(input())

lines = []
for _ in range(N):
    lines.append(list(map(int, input().split())))

lines = sorted(lines, key=lambda x:x[0])

end = []
for s, e in lines:
    end.append(e)

res = []
for e in end:
    a = bisect.bisect_left(res, e)
    if a == len(res):
        res.append(e)
    else:
        res[a] = e
        
print(len(end)-len(res))