파이썬 | 백준 | 2352 | 반도체 설계

solution

1. 1365 꼬인 전깃줄하고 비슷한 유형 https://li-fo.tistory.com/50?category=921537

2. LIS의 길이 출력

# 2352, 반도체 설계
import sys
input = sys.stdin.readline

def lower_bound(s, e, v):
    while s < e:
        m = (s+e) // 2
        if lst1[m] < v:
            s = m + 1
        else:
            e = m
    return e

n = int(input())
port = list(map(int, input().split()))
lst1 = []

for i in range(n):
    if i == 0:
        lst1.append(port[i])
    else:
        if port[i] > lst1[-1]:
            lst1.append(port[i])
        else:
            tmp = lower_bound(0, len(lst1), port[i])
            lst1[tmp] = port[i]

print(len(lst1))

32568KB

132ms

 

문제 출처 https://www.acmicpc.net/problem/2352

2352번: 반도체 설계