#2565번 전깃줄

문제 풀이

처음에는 자꾸만 그래프처럼 보여서 도저히 어떻게 푸는 지 감이 오지 않았다.

그래프나 트리 같은 것에 대해 두려움이 있어서 그런 것 같다.

그런데 a순으로 정렬하고 보니 사실 시작점은 정렬 후엔 큰 의미가 없었고(인덱스의 의미 정도) 최장 증가 수열이었다!

왜냐하면 전깃줄이 겹치지 않으려면 가지런해 야 하고 가지런하다는 것의 의미는 같지 않게 오름차순 정렬된다는 것과 같기 때문이다.....

https://redcubes.tistory.com/86

가장 긴 바이토닉 부분 수열

dp문제를 더 많이 찾아서 풀어야 할 것 같다.

n = int(input()) # 전깃줄의 갯수를 입력
wires = [] # 전깃줄의 연결 정보를 저장할 리스트
for i in range(n): # 전깃줄의 갯수만큼 반복
    wires.append(tuple(map(int,input().split())))
wires.sort() # A순서에 따라 정보를 정렬
a = [i[1] for i in wires] # 정렬된 순서로 B위치 수열을 만듦
# a = list(zip(*wires))[1]
# 최대 증가 부분 수열
dp = [1] * n
for i in range(n):
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i],dp[j]+1)
print(n-max(dp)) #원래 전깃줄 개수에서 빼면 제거할 최소 전깃줄이 나옴.