Passport Control

• pi기준으로 번호를 바꿔서 수열을 만들면, 결국 하려는 것은 수열을 여러개의 큐에 나눠 담았다가 다시 합치는 방식으로 정렬시키는 것이다.
  • 나연 정렬에서 스택 대신 큐를 사용한 버전이라 생각하면 된다.
• 각 큐에 들어간 원소들의 순서는 바뀔수 없으므로, 각 큐에는 증가하는 순서대로 원소들이 들어가야 하고, 이때 최소 개수의 큐를 사용해서 이 작업을 하는 것은, 수열을 최소 개수의 증가 부분 수열로 나누기와 같다.
• 수열을 커버하기 위해 필요한 증가 부분 수열의 최소 개수를 구하는 것은, longest non-decreasing subsequence의 길이를 구하는 것과 같고, 시간복잡도는 O(nlogn)이다. 구한 값이 k이하이면 정렬이 가능한 것이고, 그렇지 않으면 불가능한 것이다.

"""Solution code for "BOJ 16288. Passport Control".

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

Tags: [LIS]
"""

from teflib import seqtask


def main():
    N, k = [int(x) for x in input().split()]  # pylint: disable=unused-variable
    pi = [int(x) for x in input().split()]

    count = seqtask.length_of_longest_increasing_subsequence(pi, 'noninc')
    print('YES' if count <= k else 'NO')


if __name__ == '__main__':
    main()

• Dependency: teflib.seqtask.length_of_longest_increasing_subsequence