[백준/파이썬] 2565번: 전깃줄

문제

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

풀이

교차하는 전깃줄을 최소한으로 없애는 문제
최대 증가 부분 수열(LIS)을 찾는 문제입니다.

우선 그림과 함께 전깃줄이 교차하지 않도록 하기 위한 조건을 찾아봅시다.

A: 1, B: 8 & A: 3, B: 9 => 안 겹침
위 조합과 같이 앞에 있는 A보다 뒤에 있는 A가 클 때, 앞에 있는 B보다 뒤에 있는 B가 커야 겹치지 않습니다.

A: 1, B: 8 & A: 2, B: 2 => 겹침
반대로 앞에 있는 B가 뒤에 있는 B보다 크기 때문에 겹치게 됩니다.

우선 입력된 전기줄을 A 기준 오름차순으로 정렬을 해주어 위 그림과 같은 형태가 되도록 해줍니다.

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
arr.sort()

그 다음 뒷 순서의 전기줄이 앞 순서의 전기줄보다 클 때를 기준으로 dp 배열에 저장해줍니다.

dp = [1] * n
for i in range(1,n): # i번째 전기줄
    for j in range(i): # i번째보다 앞에 있는 전기줄
        if arr[i][1] > arr[j][1]: # i번째 전기줄과 j번째 전기줄이 겹치지 않는다면
            dp[i] = max(dp[i], dp[j]+1) # dp 배열에 겹치지 않는 전기줄을 저장

dp 배열에 겹치지 않는 전기줄의 개수를 저장했기 때문에 결과는 (전체 전기줄 - 겹치지 않게 배치할 수 있는 전기줄)로 출력해야 결과가 올바르게 나오게 됩니다.

print(n - max(dp)) # 전체 - 최대 개수

코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [1] * n
arr = [list(map(int,input().split())) for _ in range(n)]
arr.sort()

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

print(n - max(dp))