요세푸스가 겪은 일화에서 유래된 문제인 요세푸스 문제. 요세푸스는 의리가 없는 놈이었다..;

풀이 방법은 대강 아래와 같음

  • 제일 쉬운 방법: circular queue를 만들어서 iterating + erase
    -> 느리고 n이 큰 경우 메모리 많이 차지함
  • 약간 더 좋은 방법: 위 방법에서 iterating에 index mod를 적용
    -> 여전히 메모리는 많이 차지함
  • 치트키: 점화식을 이용
    -> 마지막 생존자를 빠르게 찾을 수 있다

초항과 일반항은 위와 같다. 유도하는 건 여기 참고. 내일 복귀라 정리하기 싫당

반응형