테페리넷

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

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

===== 풀이 =====
  * [[ps:요세푸스 문제|요세푸스 순열]]을 출력하는 문제
  * 1~n까지의 수를 실제로 생성해서 k번째 수들을 하나씩 지워가면서 출력한다. [[ps:Order Statistic Tree]]를 사용하면 지워야 할 수를 찾아서 지우는 것을 O(logn)에 처리할 수 있다. 총 시간복잡도는 O(nlogn)이 된다. 
  * 하지만 n의 크기제한이 작다보니 실제로는 O(n^2) 로 구현한 코드들이 더 빨리 돌아간다. [[ps:problems:boj:1168]] 문제는 이 문제와 동일하지만 n의 크기제한을 늘려서 반드시 O(nlogn) 솔루션으로만 풀리도록 바뀌었다.

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

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

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:실버_5}}