백준 2565 : 전깃줄 (Python)

본문 링크

import sys
input=sys.stdin.readline

T=int(input())
L=[]
for i in range(T):
    a,b=map(int,input().split())
    L.append([a,b])

L.sort(key=lambda x:x[0])

dp=[0]*T

for i in range(T):
    for j in range(i):
        if L[i][1]>L[j][1] and dp[i]<dp[j]:
            dp[i]=dp[j]
    dp[i]+=1

print(T-max(dp))

📌 어떻게 접근할 것인가?

모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력하는 문제이다.
단순하게 생각하자면 왼쪽 전기줄을 정렬하면 왼쪽전기줄은 서로 엉킬일이 없어진다.
즉 오른쪽 전기줄만 신경쓰면된다.

따라서 왼쪽 전기줄을 정렬했을때 오른쪽 전기줄의 가장 긴 증가하는 부분수열의 길이 를 구하면 된다.

📌 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence)

혹여나 LIS 알고리즘에 대해 처음들어본다면 가장 긴 증가하는 부분수열 문제 <- 이 문제를 먼저 풀어보도록하자.

먼저 $L.sort(key=lambda x:x[0])$ 으로 왼쪽전기줄에 대해 정렬해준다.
이후 $DP$ 테이블을 만들어주고 $LIS$ 알고리즘을 통해 가장 긴 증가하는 부분수열의 길이를 구하자.

따라서 전깃줄의 길이에다가 가장 긴 증가하는 부분수열을 뺀 값이 우리가 구하고자 하는 전깃줄의 최소 개수를 구할수 있다.

총 $O(N^2)$ 의 시작복잡도가 필요하다.