사용자 도구

사이트 도구


ps:problems:boj:11866

요세푸스 문제 0

ps
링크acmicpc.net/…
출처BOJ
문제 번호11866
문제명요세푸스 문제 0
레벨실버 4
분류

Order statistic tree

시간복잡도O(nlogn)
인풋사이즈n<=1000
사용한 언어Python
제출기록29200KB / 72ms
최고기록52ms
해결날짜2021/08/09

풀이

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

코드

"""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()

토론

댓글을 입력하세요:
S᠎ J Z᠎ D V
 
ps/problems/boj/11866.txt · 마지막으로 수정됨: 2021/08/09 13:49 저자 teferi