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

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

1365번: 꼬인 전깃줄

 

풀이

사용한 알고리즘 : 이진 탐색, LIS(Longest Increasing Subsequence)

 

풀이 전략

1. 첫 번째 입력한 수를 비어있는 result 리스트에 추가한다.

2. i 번째 입력한 수가 result의 맨 끝값보다 크면 result 리스트에 추가한다.

3. i 번째 입력한 수가 result의 맨 끝값보다 작으면 result 내부를 이진탐색하여,

   해당 수보다 크거나 같은 제일 작은 수를 i번째 입력한 수로 교체한다.(Lower bound 사용)

4. 전봇대 개수(n) - result 리스트가 가진 수의 개수(len(result)) 를 출력한다.

 

아래는 N=8, arr = [ 2, 6, 8, 9, 3, 4, 5, 7 ] 의 입력이 주어졌을 경우의 예시이다.

 따라서 answer = n - len(result) = 8 - 5 = 3

 

제출 코드

import bisect
import sys

input = sys.stdin.readline

n=int(input())

arr=list(map(int,input().split()))
result=[arr[0]]

for i in range(1,n):
    if result[-1]<arr[i]:
        result.append(arr[i])
    else:
        result[bisect.bisect_left(result,arr[i])]=arr[i]

print(n-len(result))