테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 꼬인 전깃줄 ======

===== 풀이 =====
  * [[ps:가장 긴 증가하는 부분 수열]] 문제이다. LIS만 남기고 나머지 전깃줄을 자르면 된다. 그렇게 하면 답은 전체 갯수에서 LIS의 길이를 뺀 것으로 구할수 있고, LIS의 길이는 이분탐색으로 O(nlogn)에 구할수 있다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 1365. 꼬인 전깃줄".

- Problem link: https://www.acmicpc.net/problem/1365
- Solution link: http://www.teferi.net/ps/problems/boj/1365

Tags: [Longest increasing subsequence]
"""

import bisect


def lis_length(seq):
    arr = [seq[0]]
    for val in seq:
        if val > arr[-1]:
            arr.append(val)
        else:
            arr[bisect.bisect_left(arr, val)] = val
    return len(arr)


def main():
    N = int(input())
    nums = [int(x) for x in input().split()]
    print(N - lis_length(nums))


if __name__ == '__main__':
    main()

</dkpr>

{{tag>BOJ ps:problems:boj:골드_2}}