2565번. 전깃줄

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

선행문제: 11053번

 

 

LIS 기초 문제인 11053번을 풀어봤다면 어려울 것이 없는 문제이다.

뭔가 복잡할 것 같지만, 어느 순간에 전깃줄이 교차하는지를 생각해보면 된다.

전깃줄은 '다른 애들이 증가하고 있는데 혼자 감소하면' 교차한다.

즉, 다른 애들은 증가하고 있는데 지들만 감소하고 있는 아이들을 찾으면 되는데,

이것은 가장 긴 부분 증가 수열을 뺀 나머지들이다. (증가수열에 속하지 않으면 감소하는 애들일 것이므로)

 

파이썬 코드이다.

import sys
import operator

numCable = int(sys.stdin.readline())
cable = []

for i in range(numCable):
    start, end = map(int, sys.stdin.readline().split())
    cable.append([start, end])  # start는 왼쪽 전봇대, end는 오른쪽 전봇대
cable.sort(key=operator.itemgetter(0))  # 기준을 왼쪽으로 삼고 정렬한다. 

increasing = [1]  # 각 원소마다 증가 부분 수열 갯수를 저장

for now in range(1, numCable):
    candidates = [0]
    for before in range(now):
        if cable[before][1] < cable[now][1]:
            candidates.append(increasing[before])
    increasing.append(max(candidates)+1)

maxIncreasing = max(increasing)
cableToCut = numCable-maxIncreasing
print(cableToCut)