줄세우기

• 가장 긴 증가하는 부분 수열 (LIS; Longest Increasing Subsequence)의 크기를 구해서, N에서 빼주면 된다. (정렬 문제 참고)
• LIS만 구하면 되므로, 시간복잡도는 O(nlogn)

"""Solution code for "BOJ 2631. 줄세우기".

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

Tags: [LIS]
"""

from teflib import seqtask


def main():
    N = int(input())
    nums = [int(input()) for _ in range(N)]
    print(N - seqtask.longest_inc_subseq(nums))


if __name__ == '__main__':
    main()

• Dependency: teflib.seqtask.longest_inc_subseq