백준 2565 전깃줄 - 파이썬

문제.

 

 

풀이.

2차원 배열로 입력을 받고 A또는 B 기준으로 정렬을 하고

A 기준으로 정렬을 했다면 B에 대하여 LIS를 구하여서 n 값에서 LIS를 빼면 된다.

B 기준으로 정렬을 했다면 A에 대하여 LIS를 구하고 n 값에서 LIST를 뺀다.

 

소스코드.

import sys

n = int(sys.stdin.readline())
wire = []
dp= [0] * n

for i in range(n):
    A, B = map(int, sys.stdin.readline().split())
    wire.append([A, B])

wire = sorted(wire, key = lambda x: x[0])

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

print(n - max(dp))