🟩 [백준] [Python] [Gold5] 2565번_전깃줄

문제

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

2565번: 전깃줄

풀이

# 백준 2565번 문제 - 전깃줄
n = int(input())
line = sorted([list(map(int, input().split())) for _ in range(n)])
dp = [1] * n
for i in range(n):
    for j in range(i):
        if line[i][1] > line[j][1]:
            dp[i] = max(dp[i], dp[j] + 1)
print(n - max(dp))

DP 문제이다. 

전깃줄을 A 기준으로 정렬 후 B에 대하여 가장 긴 증가하는 부분 수열을 구하면 된다. 

여기서 가장 긴 증가하는 부분 수열을 구해야 하는 이유는 증가하는 수열이라면 전깃줄이 교차되는 일이 발생하지 않는다.

따라서 부분 수열의 최댓값은 즉, 제거하지 않아도 되는 전깃줄이 되는 것이다. 

그러므로 n개의 전깃줄에서 제거하지 않아도 되는 전깃줄을 빼면 제거해야 하는 전깃줄이 나온다.

 

 

이러한 풀이를 떠올리는데 너무 복잡하게 생각해서 어려움이 있는 것 같다.