[백준] 1365. 꼬인 전깃줄 - Python

[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 문제.

아래 문제들과 거의 동일하다. 따로 설명을 적지 않겠음.

[백준] 2565. 전깃줄 - Python

[백준] 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)))

풀이

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

[백준] 1365. 꼬인 전깃줄 - Python

풀이

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

	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)))