[Baekjoon] 2565. 전깃줄

🔗 Problem Link

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

---

❔Thinking

• 전봇대 A와 B를 연결하는 전깃줄이 겹치지 않도록 몇개를 제거할 때, 최소한의 개수를 반환한다.

---

💻Solution

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

N = int(input().rstrip())
left = []
for _ in range(N):
    A, B = map(int, input().split())
    left.append([A,B])

left.sort()

def cross_check(line_list:list):
    prev = [line_list[0][1]]
    for a, b in line_list:
        if prev[-1] < b:
            prev.append(b)
        else:
            prev[bisect_left(prev, b)] = b
    return len(line_list) - len(prev)

print(cross_check(left))

---

🗝️keypoint

1. 최장 증가 수열 (LIS)를 찾는 문제와 동일하다.
2. 총 전깃줄의 개수에서 최장 증가 수열의 개수을 빼면, 제거하는 전깃줄의 수가 나온다.