[BOJ][Python][실1][2565] 전깃줄

문제 링크

문제링크

첫 번째 풀이

정답 코드

A에서 B로가는 전깃줄을 정렬을 합니다. 전깃줄이 시작하는 A의 위치가 정렬되어 있을 때, 도착하는 B의 인덱스가 가장 긴 증가하는 부분 수열인 경우가 정답입니다. 지워야하는 갯수를 물어보기 때문에 n - len(LIS)가 정답입니다. LIS를 구하는 방법은 여기에 있습니다.

import sys
from math import sqrt, ceil
from bisect import bisect_left, bisect_right
from operator import itemgetter

# sys.stdin = open("input.txt", "r")
n = int(input())
# R, C, K = n, 2, 1
# dp = [[0] * C for _ in range(R)]
# dp = [[[0] * K for _ in range(C)] for _ in range(R)]
# MOD = 1000000000

arr = []
for _ in range(n):
    arr.append(list(map(int, sys.stdin.readline().split())))

arr.sort(key=itemgetter(0, 1))

dp = [arr[0][1]]
arr = arr[1:]
for x in arr:
    if dp[-1] < x[1]:
        dp.append(x[1])
    else:
        dp[bisect_left(dp, x[1])] = x[1]

print(n - len(dp))

Success Notice: 수고하셨습니다.