원탁의 기사

#About

아서왕(king Arthur)은 자기 딸과 결혼시킬 기사(knight) 한 사람만 남기고 모두 죽이기로 하였습니다.

자기가 빠진 12명의 기사를 원탁에 둘러앉히고, 1번 기사를 지나 2번 기사를 죽였습니다.

3번 기사를 지나 4번 기사를 죽였습니다. 이렇게 원탁을 돌면서 하나 건너 하나씩 죽였습니다.

결국 마지막 9번 기사만이 살아남아서 공주와 결혼하고 아서왕의 뒤를 이어 왕이 되었습니다.

 n명의 기사가 있다면 몇 번째 기사가 살아남아서 공주와 결혼하고 왕이 될까요?

---

문제의 배경

이 문제의 원형은 요셉의 문제(Josephus problem)이다. 요셉의 문제를 간추리면 다음과 같다.

'1세기 경, 40명의 이스라엘 독립군이 로마군에 쫓겨 동굴에 갇히자, 한 사람씩 건너뛰는 방법으로 모두 자살하기로 한다.

허나 마지막 한 사람은 자살하지 않고 로마군에 항복하여 살아난다. 그가 요셉이다. 

그는 계산된 위치에 서 있었기 때문이다. 사람 수에 따른 요셉의 위치는 어디 이겠는가?'

---

#Solution

일단 수작업으로 조사를 해보면 아래와 같이 기사의 수에 따른 생존자 위치를 확인할 수 있다

기사의 수	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
생존자 위치	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1	3	5	7	9

규칙을 확인해보면 기사의 수 보다 작은 동시에 가장 가까운 2의 n제곱 만큼이 생존자 위치임을 확인할 수 있다

ex) 기사의 수가 4명이라면 2의 2제곱이므로 1,3이 생존자 위치가 된다

ex) 기사의 수가 8명이라면 2의 3제곱이므로 1,3,5가 생존자 위치가 된다

ex) 기사의 수가 16명이라면 2의 4제곱이므로 1,3,5,7가 생존자 위치가 된다

① 기사의 수	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
② 2**n	1	2	2	4	4	4	4	8	8	8	8	8	8	8	8	16	16	16	16	16
(①- ②)	0	0	1	0	1	2	3	0	1	2	3	4	5	6	7	0	1	2	3	4
생존자 위치	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1	3	5	7	9

(①- ②)와 생존자 위치에 대한 규칙을 확인해보면 (①- ②) * 2 + 1이 생존자 위치임을 알 수 있다.

즉, 기사의 수를 n이라하면, n에서 n이하의 가장 큰 2의 제곱수를 빼고, 그 수에 2를 곱한 다음, 1을 더하면 생존 위치이다.

예를 들어 n=12이면, 12이하인 가장 큰 2의 제곱수는 8이므로 생존위치 = (12-8)*2+1=9가 되며 알고리즘으로 표현한 것은 다음과 같다

knight = int(input('기사의 수를 입력하시오 : '))
i,j = 2,0

while (i**j<=knight): #기사의 수보다 작거나 같은 동시에 가장 가까운 i의 j제곱일때 까지 루프 반복
    square = i**j #i의 j제곱을 square 변수에 할당
    j+=1 #loop를 위한 +1 카운트

life_location = (knight-square)*i+1 #생존자 위치가 결정되는 규칙

print ("생존자 위치는 {}번째 입니다".format(life_location))

[코드 1] - 원탁의 기사 코드

위와 같은 방법으로도 결과 값인 생존자 위치를 얻을 수 있지만 또 다른 방법으로도 가능하다.

 

n이하인 가장 큰 2의 제곱수는 2진수로 바꾸었을 때 가장 왼쪽(MSB)의 비트에 해당한다

그러므로 생존자 위치는 n을 2진수로 바꾸어 가장 왼쪽의 1을 떼어내어 오른쪽 끝에 더하면 된다.

ex) 12(10진수) ---> 1100(2진수), MSB를 떼어내면 100, 오른쪽 끝(LSB 위치)에 1을 더하면 1001(2진수) 즉, 9이다.

이러한 작업을 left rotate라고 하며 정리하면, n명의 기사가 있을 때의 생존자 위치는 n을 2진수로 바꾸어 1회 left rotate한 위치이다.

knight = int(input('기사의 수를 입력하시오 : '))

binary = bin(knight) #a='0b1100'
rotation=int(binary[3:]+binary[2],base=2)

print("생존자 위치는 {}번째 입니다".format(rotation))

[코드 2] - 다른 방법의 원탁의 기사 코드

[그림 1] - 코드 결과