백준 2565번 - 전깃줄 (LIS / DP / 이분 탐색) 파이썬

📌 백준 2565번 - 전깃줄 (LIS / DP / 이분 탐색)

✨ 문제 요약

두 전봇대(A, B)가 있고, 각각의 전깃줄이 A의 위치와 B의 위치를 쌍으로 갖는다.
전깃줄이 서로 교차하지 않도록 하기 위해 최소 몇 개를 제거해야 하는지 구하는 문제다.

---

🧠 문제 해석

• 전깃줄이 교차하지 않으려면 A에서의 순서가 증가할 때, B에서도 증가해야 한다.
• 즉, A를 기준으로 정렬하면
  남은 B 값들이 가장 긴 증가하는 부분 수열(LIS)이 되도록 전깃줄을 선택하면 됨.

---

✅ 정답 로직

1. 전깃줄 목록을 A 기준으로 오름차순 정렬한다.
2. 정렬된 리스트에서 B 값들만 추출한다.
3. B 값들에서 LIS를 구한 뒤,
4. 전체 전깃줄 수 - LIS 길이 = 제거할 전깃줄 수

---

🧱 DP 풀이 (O(N²))

N = int(input())
arr = [tuple(map(int, input().split())) for _ in range(N)]
arr.sort()

dp = [1] * N

for i in range(N):
    for j in range(i):
        if arr[i][1] > arr[j][1]:
            dp[i] = max(dp[i], dp[j] + 1)

print(N - max(dp))

---

⚡️ 이분 탐색 풀이 (O(N log N), DP 없이)

import bisect

N = int(input())
arr = [tuple(map(int, input().split())) for _ in range(N)]
arr.sort()

lis = []

for _, b in arr:
    idx = bisect.bisect_left(lis, b)
    if idx == len(lis):
        lis.append(b)
    else:
        lis[idx] = b

print(N - len(lis))

• DP 배열 없이도 LIS 길이만 유지하면 정답 가능!
• 시간복잡도는 O(N log N)

---

🤔 내가 처음 시도한 코드

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

result = set()
for i in range(N - 1):
    for j in range(i + 1, N):
        if arr[i][0] < arr[j][0] and arr[i][1] > arr[j][1]:
            result.add(i)
            break

print(len(result))  # ❌ 틀림

❗️왜 오답인가?

• 교차하는 경우만 골라 제거했지만,
  전체 조합 중 가장 많은 전깃줄을 남기는 조합이 아님
• 국소 최적이라서 전체 최적을 보장하지 않음

---

🧩 배운 점

• LIS는 증가/감소 관계를 만족하는 최대 부분 수열의 길이를 구할 때 쓰인다
• 전깃줄 문제는 LIS와 매우 직결되는 조합 최적화 문제
• 정석 DP 외에도 이분 탐색으로 LIS 길이만 추적하는 방법도 가능하다

---

🎓 정리

항목 설명

문제 유형	LIS (Longest Increasing Subsequence)
정렬 기준	A 오름차순 정렬 후 B에서 LIS
핵심 알고리즘	DP (O(N²)) 또는 이분 탐색 (O(N log N))
정답 계산	전체 전깃줄 수 - LIS 길이

---

🏷 해시태그

#DP #LIS #전깃줄 #백준2565
#동적계획법 #이분탐색 #최장증가부분수열
#백준Python #알고리즘공부