| [ QuizWit ] in KIDS 글 쓴 이(By): khjeong (mathwhiz) 날 짜 (Date): 1997년11월01일(토) 16시18분36초 ROK 제 목(Title): Re : Re: Game] 돌 줍기, [A]돌줍기... 먼저 게임의 법칙에 대한 Reply. 바로 앞사람의 두 배까지만 집을 수 있습니다. 지금까지의 합계나, 상대방의 합계가 아니라, 집을 수 있는 돌의 개수는, 정확히 이전 판에만 의존합니다. ----------------------------------------------- 둘째, tree (꿈나무) 님의 해답에 대한 Reply. tree 님의 수열의 일반항을 나열해보면, n(0)=2, n(1)=3, n(2)=5, n(3)=8, n(4)=13, n(5)=20 이 됩니다. 해보면 알지만, n(4)까지는 맞습니다. 하지만, 처음 20개의 돌을 가지고 시작하면, 유감스럽게도 갑이 이기는 알고리즘이 있습니다. 먼저 갑이 2 개를 집습니다. 현재 18 개 남았죠? ( ) 안의 숫자는 현재 남은 돌의 개수라고 하면, 다음 네 가지 경우를 통해 갑은 13개의 돌을 남길 수 있습니다. 을 갑 을 갑 경우 1 : 1 (17) 1 (16) 1 (15) 2 (13) 경우 2 : 1 (17) 1 (16) 2 (14) 1 (13) 경우 3 : 2 (16) 3 (13) 경우 4 : 3 (15) 2 (13) 경우 3에서 보듯이 을은 기껏해야 6 개의 돌을 집을 수 있습니다. 계속해서 을 갑 을 갑 6 ( 7) 7 ( 0) : 끝 5 ( 8) 8 ( 0) : 끝끝끝 <== 요기 눈여겨볼 것. 4 ( 9) 1 ( 8) 3 (10) 2 ( 8) 2 (11) 3 ( 8) 1 (12) 1 (11) 1 (10) 2 ( 8) 1 (12) 1 (11) 2 ( 9) 1 ( 8) 갑은 끝을 내든지, 아니면 8 개를 남겨둘 수 있습니다. 이런 경우, 갑이 이기는 것은 너무나도 당연하므로 생략합니다. 즉, tree 님의 답은 제 6항 --- n(0)부터니까 (-: --- 부터 빗나갑니다. ## 문제 풀 때 주의할 점 : 위에서 8개를 남기면 이긴다고 했죠? 하지만, '끝끝끝'에서 보는 것처럼, 꼭 그런 것은 아닙니다. 8개를 남겨도 기술적으로, 즉 3개 이내로 집어서 남겨야 하는 것입니다. 그래서 알고리즘이 중요한 것이지요. -- I owe YOU the sunlight in the morning. |