Ocean View (Large)

• Ocean View (Small)의 라지 버전. 풀이 및 코드는 동일하다.
  • 라지버전임에도 불구, 가장 긴 증가하는 부분 수열 (LIS; Longest Increasing Subsequence)를 O(n^2)으로 구하더라도 충분히 통과한다

"""Solution code for "BOJ 12355. Ocean View (Large)".

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

Tags: [lis]
"""

import sys
from teflib import psutils
from teflib import seqtask


@psutils.gcj_style
def main():
    N = int(sys.stdin.readline())
    h = [int(x) for x in sys.stdin.readline().split()]
    print(N - seqtask.longest_inc_subseq_length(h, strict=True))


if __name__ == '__main__':
    main()

• Dependency: teflib.seqtask.longest_inc_subseq_length