[BOJ] 2565 - 전깃줄 (Python)

 

 

아이디어

 

전깃줄이 교차하지 않으려면 전깃줄들이 연결된 A의 위치 값이 증가할 때 B의 위치 값도 증가해야 한다.

따라서 전깃줄들을 A의 위치 값 기준으로 오름차순으로 정렬하고, B의 위치 값이 증가하는 가장 긴 수열의 길이를 구한다.

 

 

풀이

 

전깃줄이 연결된 A의 위치 값과 B의 위치 값을 튜플로 리스트 line에 저장하고, line을 오름차순 정렬한다.

 

1로 채워진 N 크기의 리스트 dp를 생성하고, dp에 증가하는 수열의 가장 긴 길이를 저장해 나간다.

j 번째 전깃줄이 연결된 B의 위치 값이 i 번째 전깃줄이 연결된 B의 위치 값보다 크고, dp[i]+1와 비교해 dp[j]를 갱신한다.

 

마지막에 전체 전깃줄 개수 N에서 가장 긴 증가하는 수열의 길이 max(dp)를 뺀 값을 출력한다.

 

import sys

input = sys.stdin.readline

N = int(input())
line = []
for _ in range(N):
    a, b = map(int, input().split())
    line.append((a, b))
line.sort()
dp = [1]*N
for j in range(N):
    for i in range(j):
        if line[j][1] > line[i][1]:
            dp[j] = max(dp[j], dp[i]+1)
print(N-max(dp))