[백준] 2352. 반도체 설계 - Python

[Gold II]

 

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

2352번: 반도체 설계

 

풀이

[백준] 2565. 전깃줄 - Python 문제와 동일하다시피 한 문제이다.

다만, 전깃줄 문제는 O(N^2)의 LIS (DP)로 풀이할 수 있는 반면,

이 문제는 n <= 40,000 이기 때문에, O(NlogN)의 LIS (Binary Search)로만 풀이할 수 있다.

 

입력되는 숫자는 차례로 1번 포트에 연결되어야 하는 포트 번호, 2번 포트에 연결되어야 하는 포트 번호, 3번 .... 이기 때문에, 새로이 연결하는 목적지 포트가 이미 연결한 목적지 포트들보다 더 작은 숫자라면, 교차하게 된다. 따라서, LIS의 길이를 구해주면 되는 문제.

 

AC.

import bisect
n = int(input())

lines = list(map(int, input().split()))

# lines의 LIS 길이를 구하면 됨.
res = []
for i in lines:
    a = bisect.bisect_left(res, i)
    if a == len(res):
        res.append(i)
    else:
        res[a] = i
        
print(len(res))