[백준/BOJ] - 2565번 python 풀이 - dp

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

2565번: 전깃줄

---

 

 

문제의 입력은 랜덤하게 전깃줄이 주어지므로 해당 전깃줄 정보를 하나의 list에 저장시킨 후, 정렬한다.

그럼 그림1과 같이 직관적으로 확인이 가능하다.

 

문제에서 원하는 것은 서로 교차하지 않게 없애야하는 전깃줄의 개수.

문득 든 생각 중 하나가 각 구간마다 가능한 연속된 전깃줄의 수를 dp에 저장하는 법.(이전 값과 비교하며 갱신하는 것.)

만약 dp 값이 3인 값의 번호와 비교했을 때, 해당 기준 전깃줄의 값이 더 높다면. dp+1의 값을 해당 기준 전깃줄 dp에 저장하는 방식이다.

 

만약 idx 5번 전깃줄을 기준으로 확인한다! 하면 1~4번 idx의 전깃줄의 B 값을 확인해야한다.

결과적으로 idx 1~4번의 B 값보다 기준 전깃줄의 B값이 더 클 경우, idx 1~4 dp 값의 최댓값 보다 1 보다 더 큰 값이

5번 전깃줄 dp에 저장되는 방식.

 

해당 알고리즘은 LIS 알고리즘이라고 한다.

---

 

import sys
input = sys.stdin.readline

n = int(input())
arr = []
for _ in range(n):
    a,b = map(int,input().split())
    arr.append([a,b])    

arr.sort() #비교하기 쉽게 정렬
dp = [1]*n
for i in range(1,n): #기준값
    for j in range(0,i): #기준값 보다 앞에 있는 값(훑을 값)
        if arr[i][1] > arr[j][1]:(B값 확인)
            dp[i] = max(dp[i],dp[j]+1) #1 cycle에 j 값을 전부 비교할 것이므로 max로 계속해서 갱신필
print(n - max(dp))