[Python] 백준 2565번 전깃줄

---

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

2565번: 전깃줄

---

위와 같은 상황에서 전깃줄이 겹치지 않도록 할 때, 제거해야 할 전깃줄의 최소 개수를 구해야 한다.

전깃줄이 겹치면 안되므로 증가함수의 형태를 띄어야 하고, 그 중 가장 길이가 긴 부분 배열의 길이를 구해서 전체 배열의 길이에서 빼면 해결된다.

따라서 Binary Searh를 활용한 LIS 알고리즘으로 문제를 해결한다.

import sys

input = sys.stdin.readline

n = int(input())
arr = sorted([list(map(int, input().split())) for _ in range(n)])


# Binary Search 후 값이 들어갈 idx 반환
def BS(arr, s, e, n):
    while s < e:
        m = (s + e) // 2
        if n > arr[m]:
            s = m + 1
        else:
            e = m
    return e


# 다음 항목이 부분 배열의 마지막 항목보다 크다면 끝에 붙이고,
# 작다면 적절한 위치를 BS를 통해 구하여 해당 위치에 삽입한다. <- 최대 길이 유지 가능
def LIS(arr, l):
    li = []
    max_len = 0
    for i in range(l):
        if i == 0:
            li.append(arr[i][1])
            max_len = 1
        else:
            if arr[i][1] > li[-1]:
                li.append(arr[i][1])
                max_len = max(max_len, len(li))

            elif arr[i][1] < li[-1]:
                idx = BS(li, 0, len(li), arr[i][1])
                li[idx] = arr[i][1]
    return max_len


ans = LIS(arr, n)
print(n - ans)