[BOJ] 전깃줄

---

코드

import sys
input = sys.stdin.readline

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

dp = [1]*N
for i in range(N):
    for j in range(i, -1, -1):
        if lines[i][1] > lines[j][1] and dp[i] <= dp[j]:
            dp[i] = dp[j]+1

print(N - max(dp))

결과

풀이 방법

• 분류: DP, 정렬
• 전봇대 A를 기준으로 입력받은 순서쌍 (A, B)를 오름차순 정렬한 다음, 전봇대 B를 기준으로 가장 긴 증가하는 부분수열을 구하고 전깃줄의 총 개수에서 빼면 된다.

---