문제 출처 : https://www.acmicpc.net/problem/2565

---

문제 파악

두 전봇대가 있고, 이 사이에 있는 전깃줄들이 교차되지 않게 없애야 할때, 없애야 하는 최소 개수를 출력해야 한다.

그리고 이 문제를 dp로 풀고자 한다.
어떻게 풀 수 있을까

앞서 제시했던 요령이 가장 긴 수열(LCS) 이었기 때문에 방법이 하나 떠올랐다.

우선 입력받은 전깃줄 번호들을
[[1, 8], [3, 9], [2, 2], [4, 1], [6, 4], [10, 10], [9, 7], [7, 6]]

정렬 해준다.

파이썬에서 배열에 정렬은 인덱스가 빠른 애를 기준으로 오름차순 정렬해주기 때문에
sorted(array) 해주면
[[1, 8], [2, 2], [3, 9], [4, 1], [6, 4], [7, 6], [9, 7], [10, 10]]
이렇게 정렬된다.

그렇다면 이때 이 각 배열에 인덱스 0번째를 dp테이블에 인덱스로 보고, 각 배열에 1번째를 값으로 본 후 가장 증가하는 수열의 길이를 구해주면 되지 않을까?

A 라는 리스트를 만들고 정렬된 array[i][1]을 A에 append 해준뒤,

LCS 문제처럼 dp 테이블을 채우면 가장 큰 증가하는 수열의 길이, 즉 겹치지 않는 전깃줄의 개수를 구할 수 있다.

하지만 우리가 구해야 하는 것은 잘라야하는 전깃줄의 개수이기 때문에 N에서 빼주게되면 답이 되겠다.

---

해답 코드

import sys
input = sys.stdin.readline

N = int(input())

array = []

for _ in range(N):
    a, b  = map(int,input().split())
    array.append([a,b])

sorted_array = sorted(array)

A = []

for i in range(N):
    val = sorted_array[i][1]
    A.append(val)

dp = [1]*N

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

print(N-max(dp))