[백준] 2568 전깃줄 - 2, python

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

 

 

 

 

[백준] 1365 꼬인 전깃줄, python

[백준] 1365 꼬인 전깃줄, python

 

이전에는 전깃줄이 서로 교차하지않게 만들기 위해 없애햐 하는 전깃줄의 최소 개수만 구하는 문제였다면, 이번에는 없애하는 전깃줄의 번호까지 구하는 문제이다.

 

 

 

 

LIS(가장 긴 증가하는 부분 수열), python

LIS(가장 긴 증가하는 부분 수열), python

 

 

 

전깃줄의 최대 LIS를 구하고, LIS에 포함되지 않는 전깃줄을 제거하면 된다.

여기서 제거되는 전깃줄은 원본 배열에서 자신 이전의 인덱스를 저장할 prev배열을 생성한다.

prev배열을 역추적하게 되면 LIS를 구할수 있고, LIS에 포함되지 않는 전깃줄을 제거하면 된다.

 

1. lis배열이 업데이트 될때 원본 배열의 어디서 왔는지를 알기위해 원본 배열의 인덱스를  lis_index 배열에 같이 저장해준다.

2. lis배열이 업데이트 될때, pos위치에 업데이트 된다하면, lis_index[pos-1] 을 prev배열에 업데이트 해준다.

3. LIS의 마지막 요소부터 prev배열을 통해 역추적하며 LIS를 구성하는 전깃줄들을 구한다.

4. LIS에 포함되지 않는 전깃줄들을 선택한다.

 

 

 

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

n = int(input())
# a전봇대 기준 오름차순 정렬
lines = [tuple(map(int,input().split())) for _ in range(n)]
lines.sort()

lis = []
lis_index = []
prev = [-1]*n

# LIS를 구하고, prev배열 업데이트
for i,line in enumerate(lines):
    a,b = line
    index = bisect_left(lis,b)
    if index>=len(lis):
        lis.append(b)
        lis_index.append(i)
    else:
        lis[index] = b
        lis_index[index] = i
    prev[i] = -1 if index==0 else lis_index[index-1]

# prev배열을 역추적하며 LIS를 구함
lis_line = []
cur = lis_index[-1]
while cur!=-1:
    lis_line.append(cur)
    cur = prev[cur]

# LIS에 포함되지 않는 전깃줄들을 선택
answer = [lines[x][0] for x in range(n) if x not in set(lis_line)]

print(len(answer))
for a in answer:
    print(a)