[백준 2352] 반도체 설계 (Gold 2)

문제

[백준] 반도체 설계 (Gold 2)

요약

n개의 포트가 있다. 연결선이 서로 겹치지 않게 할 때, 최대 연결 개수를 구하라.

분류

• 다이나믹 프로그래밍

풀이

1. 내 풀이 (DP)

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

from bisect import bisect_left as bl

n = int(input())
arr = [0] + list(map(int, input().split()))

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

print(max(dp))