[2565번] 전깃줄

백준 2565번 전깃줄

코드 풀이

import sys

n = int(sys.stdin.readline())

dp = [1] * n

# 입력 변수를 2차원 배열로 받은 후, 첫 번째 인자를 기준으로 정렬
num = [list(map(int, sys.stdin.readline().split(' '))) for _ in range(n)]
num.sort()

# 가장 긴 증가하는 부분 수열(LTS)
for i in range(n):
    for j in range(i):
        if num[i][1] > num[j][1]:
            dp[i] = max(dp[i], dp[j]+1)

# 결과값 = n - 가장 긴 증가하는 부분 수열
result = n - max(dp)
print(result)

• 먼저 입력 변수를 2차원 배열 형태로 받은 후, 첫 번째 인자 기준으로 정렬해줍니다.
• 두 번째 인자를 기준으로 가장 긴 증가하는 부분 수열(LIS)를 이용합니다.
• 결과값 = n - 가장 긴 증가하는 부분 수열 값