백준 2565 전깃줄 - python

출처 :

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

2565번: 전깃줄

풀이 :

n = int(input())
line = []
for _ in range(n):
    line.append(list(map(int,input().split())))
line.sort()

dp = [1 for i in range(n)]

for i in range(n):
    for j in range(i):
        if line[i][1] > line[j][1]:
            dp[i] = max(dp[i], dp[j]+1)

print(n-max(dp))

 

LIS(부분 증가 수열)을 이용하면 쉽게 해결 할 수 있는 문제이다.

LIS를 이해하니 왜 이 문제가 정답율이 높은지 알 것같다.

 

문제에서 요구하는 것을 살펴보면 전깃줄이 겹치지 않게 빼줘야한다. 그러기 위해선 전봇대 A를 기준으로 오름차순으로 나열한 후에 B를 LIS로 정렬 하면 된다.

1 8 과 2 2 는 만난다.. 왜냐하면 B가 8과 2여서 (8>2) . 

2 2 와 3 9 는 만나지 않는다. 왜냐하면 (2<9) 이기 떄문이다. 

 

따라서 A의 맞게 정렬을 해준뒤 B에 대해 LIS 정렬을 해주면 dp =   1 1 2 1 2 3 4 5 를 구할 수 있다.

여기서 5가 최대로 남을 수 있는 전깃줄에 개수이므로 전체 개수 n - max(dp) 를 해준다.