BOJ - 2565 - 전깃줄

Updated:

import sys

def solution():
    N = int(input())
    number = [0] * 501
    for _ in range(N):
        A, B = map(int, sys.stdin.readline().split())
        number[A-1] = B
    dp = [0]

    for num in number:
        if dp[-1] < num:
            dp.append(num)
        else:
            low = 0
            high = len(dp) - 1
            while low < high:

                mid = (low + high) // 2
                if dp[mid] < num:
                    low = mid + 1
                elif dp[mid] > num:
                    high = mid
                else:
                    low = high = mid
            dp[high] = num

    print(N - (len(dp)-1))

solution()

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

Categories:

Updated:

Leave a comment