[코딩테스트] 백준 2565번: 전깃줄

-문제: https://www.acmicpc.net/problem/2565

2565번: 전깃줄

 

-정답 풀이: 

• 자료구조 설정

 

 

• 숫자들의 0번째 컬럼 값들이 불규칙적으로 입력돼서 어떻게 해야할지 잘 몰랐는데, sort()로 정렬하면됨(기억해두자)

 

 

• 결국 가장 긴 증가하는 부분수열 구하는 알고리즘이다. 이 수열에는 서로 교차하는 숫자가 존재 하지 않는다. 그 수가 최대이므로
• n에서 값을 빼면 최소로 교차하는 전깃줄 개수가 된다 

 

-전체풀이:

 

n=int(input())
dp=[0 for _ in range(n)]
w=[]
w_b=[]
for _ in range(n):
    w.append(list(map(int,input().split())))
    
#0번 컬럼에 숫자들 순서 맞춰서 정렬하기     
w.sort(key=lambda x:x[0])

#가장 긴 증가하는 부분수열 구하는 알고리즘     
for i in range(n):
    for j in range(i):
        if dp[i]<dp[j] and w[i][1]>w[j][1]:
            dp[i]=dp[j]
    dp[i]+=1
            
print(n-max(dp))
  
#가장 긴 증가하는 부분수열이면 교차할 수가 없음. 교차하는 거 최소니까 n에서 가장 긴수열 빼기