백준 22.02.22. 2565번 - 전깃줄

n = int(input())

wire = []
dp = [1] * n

for i in range(n):
    wire.append(list(map(int, input().split())))

wire.sort(key=lambda x: x[0])

for i in range(n):
    for j in range(i):
        if wire[j][1] < wire[i][1]:
            dp[i] = max(dp[i], dp[j] + 1)

print(n - max(dp))

• 우선 입력받을 때 전봇대의 순서가 정렬되어 입력되는 것이 아니라는 점에 유의해야 합니다.
• 따라서 정렬을 해야한다는 생각을 가지고 작성했습니다.
• 전봇대의 개수에 맞게 wire리스트에 추가해주었습니다.
  • wire리스트의 각 요소는 list형식으로 이루어져 있으며 이 것의 0인덱스는 A전봇대의 순서, 1인덱스는 B전봇대의 순서입니다.
• wire리스트에 모두 입력받았다면 wire리스트의 요소의 0인덱스(= wire[i][0] )에 따라 정렬해줍니다.
• 이것을 wire리스트의 요소의 1인덱스(= wire[i][1] )에 따라 가장 길이가 긴 오름차순 수열의 길이를 구합니다.
• 그리고 구해진 수열에서 필요없는 부분을 정답으로 출력해야하므로 "n-수열의 최대길이"를 출력해줍니다.