사용자 도구

사이트 도구


ps:problems:boj:1179

마지막 요세푸스 문제

ps
링크acmicpc.net/…
출처BOJ
문제 번호1179
문제명마지막 요세푸스 문제
레벨플래티넘 4
분류

요세푸스문제

시간복잡도O(klogn)
인풋사이즈k<=90, n<=10^15
사용한 언어Python
제출기록31480KB / 64ms
최고기록56ms
해결날짜2021/08/06

풀이

  • 마지막으로 남는 번호를 구하는 요세푸스 문제
  • 요세푸스 문제에서 설명한대로 O(n) 알고리즘과 O(klogn)알고리즘이 존재한다. 여기에서는 n값에 비해서 k값이 매우 작으므로 O(klogn)알고리즘을 사용하면 된다.
  • 재귀함수를 사용해서 구현되어 있는데, 재귀 깊이가 O(klogn)으로 최대 4500정도까지 가능하다. 따라서 파이썬으로는 setrecursionlimit을 호출해서 재귀깊이 제한을 늘려주어야만 한다.

코드

"""Solution code for "BOJ 1179. 마지막 요세푸스 문제".

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

Tags: [JosephusProblem]
"""

import sys


def josephus(n, k):
    def _josephus(n):
        if n == 1:
            return 0
        if k > n:
            return (_josephus(n - 1) + k) % n    
        res = _josephus(n - n // k) - n % k
        return res + (n if res < 0 else res // (k - 1))
    
    return (n if k == 1 else _josephus(n) + 1)


def main():
    sys.setrecursionlimit(10**6)
    N, K = [int(x) for x in input().split()]
    print(josephus(N, K))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
I F G Q N
 
ps/problems/boj/1179.txt · 마지막으로 수정됨: 2021/08/06 14:27 저자 teferi