테페리넷

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

====== 요세푸스 문제 0 ======

===== 풀이 =====
  * [[ps:problems:boj:1158]] 에서 N의 범위를 더 줄인 문제. 그런데 이미 [[ps:problems:boj:1158]] 조차도 O(n^2)의 느린 알고리즘으로도 풀리기 때문에 N을 더 줄인 문제를 추가한 의도는 잘 모르겠다. 
    * solved.ac의 난이도는 [[ps:problems:boj:1158]]가 실버 5로, 더 쉬운 문제인 이 문제는 실버4로 측정되어있다. 뭐 거기서 거기긴 하지만.. 잘못되었긴 하다;
  * [[ps:problems:boj:1158]]과 동일한 코드를 제출해서 통과했다. 풀이는 링크 참고.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 11866. 요세푸스 문제 0".

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

Tags: [OrderStatisticTree]
"""

from teflib import segmenttree


def main():
    N, K = [int(x) for x in input().split()]
    nums = segmenttree.OrderStatisticTree([1] * N)
    order = 0
    answer = []
    for _ in range(N):
        order = (order + K - 1) % nums.size()
        num = nums.kth(order + 1)
        nums.add(num, -1)
        answer.append(num + 1)

    print('<', end='')
    print(*answer, sep=', ', end='>')


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:segmenttree#OrderStatisticTree|teflib.segmenttree.OrderStatisticTree]]

{{tag>BOJ ps:problems:boj:실버_4}}