[Gold II]
https://www.acmicpc.net/problem/1365
1365번: 꼬인 전깃줄
첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가
www.acmicpc.net
풀이
Binary Search를 이용해 O(NlogN)으로 풀이하는 LIS 문제.
아래 문제들과 거의 동일하다. 따로 설명을 적지 않겠음.
[백준] 12015. 가장 긴 증가하는 부분 수열 2 - Python
AC.
import bisect
from collections import deque
import sys
input = sys.stdin.readline
print = sys.stdout.write
N = int(input())
arr = list(map(int, input().split()))
res = []
for k in arr:
a = bisect.bisect_left(res, k)
if a == len(res):
res.append(k)
else:
res[a] = k
print(str(len(arr) - len(res)))