138. 2565(전깃줄)

import sys
input = sys.stdin.readline

N = int(input())
Eline = sorted([list(map(int,input().split())) for _ in range(N)])
DP = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if Eline[i][1] > Eline[j][1]:
            DP[i] = max(DP[i], DP[j]+1)

print(N-max(DP))

문제요약

서로 교차되지 않게 할때 제거 할 전깃줄 최소 개수

설명

LIS (최장증가수열) 를 이용하면 된다.

 

DP는 설치 가능한 갯수를 뜻한다.

 

따라서 총 전깃줄 - 서로 교차되지 않는 최대의 를 해주면 제거해야할 최소의 전깃줄 개수가 나오게 된다.

 

이 문제는 정확하게 파악을 못하겠다..

따라서 비슷한 유형이 나오면 LIS를 사용해야겠다는 소스만 얻어가자.