[Platinum V]
https://www.acmicpc.net/problem/2568
2568번: 전깃줄 - 2
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결
www.acmicpc.net
풀이
이분탐색을 이용한 LIS - O(NlogN) 문제. 아래 두 문제를 참고하면 쉽게 풀이할 수 있다.
[백준] 14003. 가장 긴 증가하는 부분 수열 5 - Python
AC.
import bisect
from collections import deque
n = int(input())
lines = []
for _ in range(n):
lines.append(list(map(int, input().split())))
lines = sorted(lines, key = lambda x: x[0])
res = []
index = []
for s, e in lines:
a = bisect.bisect_left(res, e)
if a == len(res):
res.append(e)
else:
res[a] = e
index.append(a)
cnt = len(res)-1
q = deque()
for i in range(len(index)-1, -1, -1):
if index[i] == cnt:
cnt -= 1
else:
# LIS에 포함되지 않는 경우를 저장.
q.appendleft(lines[i])
print(len(lines) - len(res))
for k in q:
print(k[0])