1. 문제

출처: 백준 2565번 전깃줄

2. 풀이

증가하는 부분 수열을 이용하여 접근하면 되는 문제이다.
백준 11053번 가장 긴 증가하는 부분 수열 문제 풀이에서 가장 긴 증가하는 부분 수열을 구하는 법을 풀이해두었다.

해당 문제에서 어떤 것을 수열도 두고, 증가하는 부분 수열을 구하면 문제 풀이에 활용할 수 있는지 고민하면 된다.
교차하는 전깃줄을 없애고 싶다면, 전깃줄이 시작하는 왼쪽 부분과 전깃줄이 끝나는 오른쪽 부분의 숫자들이 모두 오름차순으로 있다면 된다.
예제의 그림에서 왼쪽의 4번에서 출발하는 전깃줄은 오른쪽의 1번에 도착하면서, 왼쪽의 1,2,3번에서 출발하는 전깃줄보다 오른쪽의 번호가 작게 되었다. 이렇게 도착하는 전깃줄을 제거하면 교차하는 것들을 없애줄 수 있다.

따라서, 입력되는 전깃줄의 값들을 A 위치 숫자에 따라서 정렬하고, B에서 가장 긴 증가하는 부분 수열이 어떻게 되는지 살펴보면 된다. 그리고 해당 길이만큼 전깃줄을 남기면 되므로, 전체 전깃줄 개수에서 부분 수열 길이를 뺀 결과를 출력하면 된다.

3. 소스코드

n = int(input())
pos = []
dp = [1]*n
for _ in range(n):
    temp = list(map(int,input().split()))
    pos.append(temp)

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

for i in range(n):
    for j in range(i):
        if pos[i][1] > pos[j][1]:
            dp[i] = max(dp[i],dp[j]+1)
print(n-max(dp))

4. 그 외

문제를 처음 보았을 때에는 교차되는 숫자를 어떻게 세야 하나 굉장히 갑갑했었다. 부분 수열을 이런 식으로도 활용할 수 있구나를 배울 수 있는 문제였다.