[백준/Python] 2565 전깃줄

문제 링크

2565번: 전깃줄

 

문제 풀이

• 정렬로 접근하다가 전에 이코테 강의에 있던 문제와 비슷하다고 생각되어 그 방식으로 접근해 보았다.
• 이 문제는 "가장 긴 증가하는 부분 수열" 문제로 생각할 수 있는데, a에 있는 전깃줄이 차례로 정렬되어 있을 때, b에 있는 전깃줄의 숫자가 차례로 정렬되어 있도록 하면 된다.
• 먼저 입력 받은 리스트를 a(x[0])를 기준으로 오름차순 정렬 후에, 같은 값이 있다면 b(x[1])를 기준으로 정렬한다.
• 이후 b에 있는 i번째의 전깃줄의 숫자(ab[i][1])가 그 이전의 숫자(ab[j][1])보다 크다면 1을 더하고(dp[j]+1), 이를 현재의 값(dp[i])과 비교하여 더 큰 값을 저장하도록 한다.
• 최종적으로 dp 리스트에 저장된 값중 가장 큰 값(max(dp))이 최대로 남아있을 수 있는 전깃줄의 개수가 되므로, 최소로 제거해야 할 전깃줄의 개수는 전체의 전깃줄의 수(n)에서 뺀 값이 된다.

 

전체 코드

import sys

n = int(sys.stdin.readline())
ab = []
for _ in range(n):
    a, b = map(int, sys.stdin.readline().split())
    ab.append([a, b])
ab.sort(key=lambda x: (x[0], x[1]))

dp = [1] * n

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

print(n - max(dp))