2565. 전깃줄 (Python)

 

2565번: 전깃줄

 

풀이 

 최장 증가 부분 수열을 활용하여 해결할 수 있다. 최장 증가 부분 수열에 관한 설명은 여기를 참고하자.

 

 A 전봇대의 1번부터 N번까지 연결되어 있는 B의 전깃줄 번호를 한 배열 안에 담아둔다. 그 배열 안에서 최장 증가 부분 수열의 길이를 구하고 이를 N에서 빼주면 없애야 하는 전깃줄의 최소 개수를 구할 수 있다.

 

코드

import heapq
from bisect import bisect_left

if __name__ == '__main__':
    N = int(input())
    q = []

    for _ in range(N):
        a, b = map(int, input().split())
        heapq.heappush(q, (a, b))

    nums = []
    while q:
        _, num = heapq.heappop(q)
        nums.append(num)

    dp = [1]
    increaseNums = [nums[0]]

    for i in range(1, N):
        if increaseNums[-1] < nums[i]:
            dp.append(dp[-1] + 1)
            increaseNums.append(nums[i])
        else:
            index = bisect_left(increaseNums, nums[i])
            increaseNums[index] = nums[i]

    print(N - dp[-1])