[BOJ 2565] 전깃줄(Python)

---

문제

전깃줄

---

문제 해설

전봇대 두 대에서 모든 전깃줄이 겹치지 않게 최소한의 전깃줄을 걷어내는 문제입니다. 그러므로 전깃줄이 겹치는 경우의 최소한을 찾거나, 전깃줄이 겹치지 않는 최대한의 경우를 찾으면 됩니다.

먼저 전깃줄이 겹치는 경우는 a -> b로 가는 전깃줄이 있다고 가정하면
a+i -> b-j 혹은 a-i -> b+j입니다.
반대로 전깃줄이 겹치지 않는 경우는
a+i -> b+j 즉, A에서 B로 가는 전깃줄의 다음 전깃줄은 전에 도착했던 위치보다 높으면 됩니다. 바꿔서 말하면 B에서 도착하는 전깃줄의 가장 긴 증가하는 부분 수열을 구하면 됩니다.

1. A 전봇대를 기준으로 오름차순 정렬을 한 뒤, 적당한 자료구조에 B에 해당하는 위치를 담습니다.
2. 해당 자료구조에 들어있는 sequence에 대해 가장 긴 증가하는 부분 수열을 구합니다.
3. 수열의 길이를 n에서 빼줍니다.

---

풀이 코드

import sys

input = sys.stdin.readline
n = int(input())
temp = []
seq = []
dp = [1] * n
for _ in range(n):
    temp.append(list(map(int, input().split())))
# A 전봇대를 기준으로 오름차순 후, B 전봇대를 담아준다.
for _, x in sorted(temp):
    seq.append(x)
# 가장 긴 증가하는 수열의 길이를 구한다.
for i in range(n):
    for j in range(i):
        if seq[i] > seq[j]:
            dp[i] = max(dp[j] + 1, dp[i])
print(n - max(dp))

---