STUDENTSKO

• 가장 강한 K명이 맨 앞에 오고, 그다음 강한 K명이 그 뒤에 오고, .. 이런식으로 정렬되어야 한다. 각각의 K명 그룹 안에서는 순서가 바뀌어도 된다.
• 그렇다면, 가장 강한 K명에 '1'을 부여하고, 그 다음 K명에 '2'를 부여하고 이런식으로 각 학생들을 그 학생이 들어가야할 그룹의 순위로 치환해서 새로운 수열을 만들면, 이제 그냥 그 수열을 정렬하는 문제가 된다.
  • 학생들의 강함 정도가 모두 다르다는 조건이 있기 때문에, 그 학생이 들어가야 할 그룹은 유일하게 결정된다. 만약 모든 값이 distinct하다는 조건이 없었다면 꽤 어려운 문제가 되었을 수도 있겠다..
  • 각 학생이 들어갈 그룹의 순위를 찾는 것은, 그냥 전체를 정렬해서 비교해서 위치를 확인하면 된다.
• 이제 수열에서 원소를 임의의 위치로 이동시키는 연산을 사용해서 정렬하기 위해 필요한 연산의 최소 횟수는, {수열의 길이} - {LIS의 길이} 로 쉽게 구할 수 있다.
• 시간복잡도는 정렬과 LIS를 구하는것 모두 O(nlogn)에 처리 가능하다.

"""Solution code for "BOJ 10547. STUDENTSKO".

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

Tags: [lis]
"""

import itertools
from teflib import seqtask


def main():
    N, K = [int(x) for x in input().split()]
    v = [int(x) for x in input().split()]

    seq = [0] * N
    sorted_inds = sorted(range(N), key=v.__getitem__)
    for group_no, inds in enumerate(itertools.batched(sorted_inds, K)):
        for i in inds:
            seq[i] = group_no

    answer = N - seqtask.longest_inc_subseq_length(seq, strict=False)
    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.seqtask.longest_inc_subseq_length