백준[ 2565 | Python ] 전깃줄

문제

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

풀이

먼저 두 개의 전봇대(A,B)가 주어진다.
이 때 전깃줄들이 교차하기 때문에 생각하기 쉽지 않은데, 이를 해결하기 위해 전봇대 A의 오름차순을 기준으로 전봇대 B들의 위치를 정렬한다. 이는 전깃줄들이 서로 겹치지 않게 하기 위함이다.

이렇게 정렬을 해주면 모든 전깃줄은 겹치지 않게되는데 이 때 전봇대 B들의 위치가 중요해진다.
B의 원소로 들어가있는 위치들이 증가하는 부분 수열로 이루어져 있다면 전기줄이 서로 겹치지 않는 다는 것을 의미하기 때문에 증가하는 부분 수열의 최장 길이를 계산하면 된다.

이후로 최종 답을 내기 위해서는 증가하는 부분수열의 최장길이를 내는 것이 아닌 제거해야할 최소 개수를 구해야하기 때문에 전깃줄의 개수 - 부분수열의 최장 길이를 구한다.

import sys
input = sys.stdin.readline
n = int(input().rstrip())
P = []
for i in range(n):
    P.append(list(map(int,input().split())))
P.sort(key= lambda x : (x[0]))
P_a,P_b = [i[0] for i in P], [i[1] for i in P]
dp = [0 for i in range(n)]
for i in range(n):
    for j in range(i):
        if P_b[i] > P_b[j] and dp[i]<dp[j]:
            dp[i] = dp[j]
    dp[i] += 1
print(n-dp(max))

생각 & 정리

dp의 원소로 어떤 것을 넣어야하는지 고민이었다.
제거해야할 개수를 구하는 것은 무리가 있다고 생각이 들었고 부분수열의 증가라는 힌트를 얻어 해결할 수 있었다.
직관적인 풀이는 슬슬 피해야할 것 같다.