[백준] 1365번 - 꼬인 전깃줄 (파이썬)

acmicpc.net/problem/1365

 

# 꼬인 전깃줄
import bisect
N = int(input())
arr = list(map(int, input().split()))

result = [arr[0]]
for i in range(1, len(arr)):
    index = bisect.bisect_left(result, arr[i])
    if index == len(result):
        result.append(arr[i])
    else:
        result[index] = arr[i]
print(len(arr)-len(result))

 

이분탐색, bisect
1. 입력을 받는다.
2. result 리스트 선언
3. arr의 각 원소마다
    - result가 비었으면 append
    - bisect_left로 result에 x가 들어갈 인덱스를 구한다.
        - index가 result의 길이라면 append
        - 아니라면 result[index] = x
4. len(result)는 가장 긴 증가하는 부분 수열의 길이이므로 전깃줄 개수에서 빼준 값을 출력

 

가장 긴 증가하는 부분 수열 문제이다.

result는 가장 긴 증가하는 부분 수열을 담는 리스트이다.

result의 길이는 현재까지 등장한 가장 긴 증가하는 부분 수열의 길이이다.

1 추가
result = [1]
8 추가
result = [1, 8]
12 추가
result = [1, 8, 12]
3 추가
result = [1, 3, 12]

len(result) = 3
result = [1, 8, 12] 일 때의 길이
4 - 3 = 1
한 개의 전깃줄만 잘라주면 된다.

 

---

<비슷한 문제>

 

[백준] 2352번 - 반도체 설계

[백준] 2352번 - 반도체 설계 (파이썬)

 

[백준] 12738번 - 가장 긴 증가하는 부분 수열 3

[백준] 12738번 - 가장 긴 증가하는 부분 수열 3 (파이썬)