백준 - 전깃줄 - 2(2568)

이것도 시리즈 문제인 듯하다.

가장 긴 증가하는 부분 수열의 알고리즘을 이용하면 된다.

dp로 하면 메모리 초과 나서

이분탐색으로 풀어주어야 한다.

제거해야 할 전깃줄 개수는 쉽게 구할 수 있었으나 요소를 구하는데 고민을 많이 했다.

lis 리스트를 하나 만들어서 최장길이 값을 넣어주고

역순으로 탐색을 해서 제거대상을 뽑아 주었다.

 

def bs_func(target):
    l,r = 0,len(bs)
    t = 0
    while l <= r:
        mid = (l+r) // 2
        if bs[mid] < target:
            l = mid+1
        else:
            r = mid-1
            t = mid
    return t
n = int(input())
data = []
for _ in range(n):
    data.append(list(map(int, input().split())))

data = sorted(data)
bs = [data[0][1]]
lis = [0]*n
lis[0] = 1
for i in range(1,n):
    if bs[-1] < data[i][1]:
        bs.append(data[i][1])
        lis[i] = len(bs)
    else:
        idx = bs_func(data[i][1])
        lis[i] = idx + 1
        bs[idx] = data[i][1]
max_count = n-len(bs)
each_count = n-max_count
answer = []
for i in range(n-1,-1,-1):
    if each_count != lis[i]:
        answer.append(data[i][0])
    else:
        each_count -= 1
print(max_count)
for i in sorted(answer):
    print(i)