Josephus Problem

n 명의 사람이 삥 둘러앉아있고 매번 k번째 사람을 execute 할 때 마지막에 살아남는 사람 구하기..

예를들어 n = 5, k = 3 이라고 하면

step1: 0, 1, 2, 3, 4 (2번 executed)
step1: 0, 1, 2, 3, 4 (0번 executed)
step1: 0, 1, 2, 3, 4 (4번 executed)
step1: 0, 1, 2, 3, 4 (1번 executed)

결국 3번이 살아남는다..


이 문제를 해결하는 방법은 그냥 무식하게 simulation 할 수 있다..
매번 남아있는 원소를 하나씩 세어가면서 k번째에서 지운다..
그런데 조금 더 생각해보면 k개를 모두 셀 필요가 없고.. k mod '남아있는 원소 개수' 까지만 세면 된다..
그러나 이렇게 하더라도 n이 클 경우 상당히 오래걸린다..

그런데 이 문제를 O(n) 만에 풀 수 있는 해법이 있다..~ (원리는 모름.. ㅠ_ㅠ)

  1 /* Josephus Porblem */
  2
  3 /*
  4 n = # of people
  5 k = every k'th person executed
  6 r = last man alive
  7 */
  8
  9 int josephus(int n, int k)
 10 {
 11     int i, r;
 12     r = 0;
 13     for (i = 1; i <= n; i++) {
 14         r = (r + k) % i;
 15     }
 16     return r;
 17 }

게다가 특별히 k = 2 인 경우에 궁극의 O(log n) 해법도 있다.. OTL ;;

관련문제:
440 - Eeny Meeny Moo


Josephus 문제의 기원 (from Wikipedia)

The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. As the legend goes, he and his 40 comrade soldiers were trapped in a cave, surrounded by Romans. They chose suicide over capture and decided that they would form a circle and start killing themselves using a step of three. As Josephus did not want to die, he was able to find the safe place, and stayed alive with his comrade, later joining the Romans who captured them. (The only statement given by Josephus himself is that by luck, or maybe by the hand of God, he and another man remained the last and gave up to the Romans.)


'Problem Solving > Algorithm notes' 카테고리의 다른 글

Finding Minimum Path Cover in DAG  (0) 2009.06.15
Plane Equation (평면의 방정식)  (0) 2009.04.16
Ellipse (타원)  (0) 2009.04.15
Modular Arithmetic 1탄 - Extended Euclid  (2) 2009.02.22
Combination 개수 구하기 (Pascal's Triangle)  (2) 2009.02.07
Josephus Problem  (2) 2009.01.01
Number of Swap Operations  (0) 2008.07.24
소수 구하는 방법 (Sieve of Eratosthenes)  (2) 2008.07.15
Horner's Rule  (0) 2008.05.04
GCD SUM  (0) 2008.03.18
Erdos & Gallai  (0) 2008.03.04

Comments

  1. 그래요 2009.01.03 12:19 Permalink Modify/Delete Reply

    안녕하세요.
    요세푸스 문제에서 O(n)만에 구하는 아이디어는 n-1명에서 시작할 때 살아남는 사람의 인덱스로,
    n명이 시작할 때 살아남는 사람의 인덱스를 추측하는 것이 아닐까 하네요 -ㅁ-
    저도 비슷한 아이디어로 대충 O(n)에 풀수있도록 정리를 하긴 했지만 저렇게 식이 깔끔하게 나오지는 않았는데 실제로 어떻게 된건지 무척 궁금합니다 +_+

    • helloneo 2009.01.04 03:01 신고 Permalink Modify/Delete

      오호.. n-1번째 index를 이용해서 n번째 index를 구하는것이었군요..~! 그나저나 wf에서도 gl & hf 하세요..~

Leave a Comment


to Top