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번: 반도체 설계
첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주
www.acmicpc.net
'알고리즘 > 이분 탐색' 카테고리의 다른 글
자바 | 백준 | 1920 | 수 찾기 (0) | 2021.02.27 |
---|---|
파이썬 | 백준 | 1365 | 꼬인 전깃줄 | LIS(최장 증가 수열) (0) | 2020.08.30 |