전깃줄 [백준 2565] - python

import sys
input = sys.stdin.readline

def BOJ2565() :
  n = int(input())
  l = []
  for _ in range(n) :
    l.append(list(map(int, input().split())))
  
  l.sort()  
  
  dp = [1 for _ in range(n)]
  
  for i in range(n) :
    for j in range(i) :
      if l[j][1] < l[i][1] :
        dp[i] = max(dp[i], dp[j] + 1)
      
  print(n - max(dp))
  

BOJ2565()

 

접근방법 :

1. A 배열을 기준으로 정렬을 해준다.

 

예시입력에서는 

1 8

2 2

3 9

4 1

6 4

7 6

9 7

10 10

 

과 같이 정렬이 될것이다.

 

2. B 배열을 기준으로 증가하는 가장 긴 배열의 길이를 구해주자

   => [1 4 6 7 10]  길이 5의 증가하는 배열

3. 전체 길이에서 증가하는 배열의 최대 길이를 빼주면 된다.

 

 

 

 

 

https://www.acmicpc.net/problem/2565

2565번: 전깃줄