문제

[백준] 전깃줄 - 2 (Platinum 5)

요약

이미지

전깃줄이 서로 겹치지 않게 한다. 한 포트에 두 개 이상의 전깃줄이 연결될 수 없다.

분류

  • 다이나믹 프로그래밍

풀이

1. 내 풀이 (DP)

a에서 b로 연결된 전깃줄을 (a, b) 튜블로 나타낼 때, a에 대해 오름차순으로 정렬한다. 그리고 여기서 b에 대해 가장 긴 증가하는 부분 수열을 구한다. O(NlogN) 알고리즘을 통해 dp 리스트를 구하고, 역순으로 순회하며 SET에 저장한다. 가장 긴 부분수열에 해당하는 b에 대해 a를 오름차순으로 출력한다.

import sys
from bisect import bisect_left as bl
input = sys.stdin.readline

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

arr = [0] + [b for a, b in lines]

dp = [0] * (n + 1)
d = [0]

for i in range(1, n + 1):
    idx = bl(d, arr[i])
    if idx == len(d):
        d.append(arr[i])
        dp[i] = idx
    else:
        d[idx] = min(d[idx], arr[i])
        dp[i] = idx

m = max(dp)
print(n - m)
ans = set()
for i in range(n, -1, -1):
    if m == dp[i]:
        m -= 1
        ans.add(arr[i])

for a, b in lines:
    if b not in ans:
        print(a)