[백준] 2565번(python 파이썬)

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

 

전깃줄을 입력을 받아서 list(tuple)형태로 만들고 key = tuple[0]값으로  역으로 정렬시킨다.

ex)

 

 

첫번쨰 원소의 [0] 값+1의 크기만큼 list를 생성한다.

dp = [1] * (link[0][0] + 1)

 

1 ~ 해당 전깃줄 갯수만큼 반복문을 돌린다.

for i in range(1, n):

 

정렬된 원소를 보면서

a = link[i][0]
b = link[i][1]

 

이전 값들중 b 값보다 큰 값들중 생성한 list의 최대값을 구한다.

for j in range(i):
    if b < link[j][1]:
        max_value = max(max_value, dp[link[j][0]])

 

list[i]에  max값을 더해준다.

dp[a] += max_value

 

 

n = int(input())
link = list()
for _ in range(n):
    link.append(tuple(map(int, input().split())))

link.sort(key=lambda x: x[0], reverse=True)

dp = [1] * (link[0][0] + 1)

def result():
    for i in range(1, n):
        a = link[i][0]
        b = link[i][1]
        max_value = 0
        for j in range(i):
            if b < link[j][1]:
                max_value = max(max_value, dp[link[j][0]])

        dp[a] += max_value

result()
print(n - max(dp))