[백준] 2565 - 전깃줄 (S1)

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

2565번: 전깃줄

개인적으로 solved.ac 난이도에 비해 힘들게 푼 DP 문제이다.

이 문제는 1가지만 떠올리면 정말 정말 쉽게 풀린다.

 

현재 문제에서 요구하는게 '없애야 하는 전깃줄 개수의 최솟값'이다.

하지만 전체 전깃줄의 개수가 고정되어 있다는 점에서 이를 뒤집어 생각하면

'남겨야 하는 전깃줄 개수의 최댓값'을 구해서 이 문제를 풀 수도 있다.

이렇게 발상의 전환만 성공했다면, 이 문제는 단순한 LIS 문제로 바뀐다.

(나는 이 발상의 전환이 생각보다 많이 힘들었다.)

 

전깃줄을 A 지점 위치 기준으로 정렬시키고

가장 작은 위치의 전깃줄부터 하나씩 순회하면서

i 번째 전깃줄을 포함하는 경우, 최대 남길 수 있는 전깃줄의 개수를 센다.

 

i 번째 전깃줄의 A 위치와 B 위치를 ia, ib 라고 하면

i 번째 전깃줄을 포함하여 최대 전깃줄 포함 갯수는

MAX ( ka < ia, kb < ib 인 k번째 전깃줄 ( 0<= k < i) 의 최대 전깃줄 포함 갯수 ) + 1 이다.

 

이 DP 식을 그대로 구현하면 O(N^2) 의 시간복잡도로 문제를 풀 수 있다.

 

한가지 주의할 점은, 마지막 출력이 n - max(dp) 이지, n - dp[-1] 가 아니라는 점이다.

이 문제의 예제가 기가막히게 오름차순형태로 dp가 쌓아지는 모양이라

dp 테이블의 가장 마지막값이 최댓값이 된다는 착각을 하기가 쉽다.

 

import sys
def solve():
    n = int(input())
    l = []
    for _ in range(n):
        l.append((tuple(map(int, input().split()))))
    l.sort()
    dp = [1 for _ in range(n)]
    for i in range(n):
        a, b = l[i]
        for k in range(i-1, -1, -1):
            _a, _b = l[k]
            if _a < a and _b < b:
                dp[i] = max(dp[i], dp[k] + 1)

    print(n - max(dp))


if __name__ == '__main__':
    solve()