[BOJ] 2565 : 전깃줄 (Python3)

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

풀이

A1과 B1이 연결되고 A2와 B2가 연결되었다고 가정할 때, 전깃줄이 교차하는 경우는 A1 > B1 and A2 < B2 혹은 A1 < B1 and A2 > B2 일 경우이다.
즉, A를 1에서 10으로 순서대로 놓을 때 B가 순서대로 위치하지 않으면 전깃줄이 교차된다.
반대로 B가 순서대로 위치한다면 전깃줄이 교차되지 않을 것이다.
교차되지 않을 전깃줄의 최대 개수를 구하면, 없애야 하는 전깃줄의 최소 개수를 쉽게 구할 수 있다. n에서 전자를 빼면 된다.

그렇다면 교차되지 않는 전깃줄의 최대 개수를 어떻게 구해야 할까?
전깃줄의 위치를 2차원 배열로 받은 뒤, A 순서에 따라 정렬한다.
그리고 B 원소 각각의 가장 긴 증가하는 부분 수열 개수를 구한다.

n에서 가장 큰 부분 수열 개수를 뺀 값이 답이 된다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
line = [list(map(int, input().strip().split())) for _ in range(n)]
line.sort(key = lambda x:x[0])

dp = [0]*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])
    dp[i] += 1

print(n - max(dp))