[백준 12015, 1365] - Python

• 취알스 4주차 정렬, 이분탐색 - 3/5

12015 가장 긴 증가하는 부분 수열 2

1365 꼬인 전깃줄

두 문제가 사실상 같은 문제다..!
꼬인 전깃줄 문제에서 답 출력하는 부분만 바꾸면 됨.

이분탐색을 이용하면 되는데 왜 이렇게 푸는건지 사실 잘 모르겠음.ㅠ

import sys
from bisect import bisect_left
n = int(input())
array = list(map(int, sys.stdin.readline().split()))
answer = [array[0]]
for i in array:
    if answer[-1] < i:
        answer.append(i)
    else:
        b_l = bisect_left(answer, i)
        answer[b_l] = i

print(len(answer)) # 가장 긴 증가하는 부분수열 2
print(n-len(answer)) # 꼬인 전깃줄

• 참고
  https://blog.naver.com/skrud3021/222221236048