[백준 2568번] 전깃줄 -2 (Python3)

import sys
input = sys.stdin.readline
from bisect import bisect_left

N = int(input())

wire = []
parent = {}

for i in range(N):
  wire.append([*map(int,input().split())])
wire.sort()

DP = [0]
DPi = [-1]

for i in range(N):
  num = wire[i][1]
  if num > DP[-1]:
    DP.append(num)
    DPi.append(i)
    parent[i] = DPi[-2]
  else:
    idx = bisect_left(DP,num)
    DP[idx] = num
    DPi[idx] = i
    parent[i] = DPi[idx-1]

check = [1]*N
x = DPi[-1]
while x != -1:
  check[x] = 0
  x = parent[x]

print(N-len(DP)+1)
for i in range(N):
  if check[i]:
    print(wire[i][0])

 

LIS 문제이다. 가장 긴 증가하는 부분수열 5와 똑같은 알고리즘으로 풀면 된다.

약간의 차이점만 언급하면

1. wire를 A번 노드의 숫자에 따라 sort 해준다.

2. LIS를 출력하는 것이 아니라 LIS를 이루지 않는 그 외 수열을 출력한다.

 

의 차이점 정도가 있을 것이다.

 

 

오늘의 교훈) LIS를 적재적소에 잘 활용하자