새로운 이론(알고리즘)을 알게되었을때의 쾌감.. 정말 오랜만이다.. live archive 3830 - John 문제를 풀어보다가 궁금했던 거였는데.. 탑코더 포럼을 보다가 우연히 해법을 알게되었다..

이와 같은 문제를 Nim Game 중에서도 Misère Nim 이라고 한다.. 전략은 Normal Nim과 같이 nim sum = 0 인 상태를 상대방에게 넘겨주면 되고.. 모든 deck의 카드의 개수가 1이 되었을때는 예외적으로 하나의 카드를 더 빼서 홀수개의 1개의 카드로 이루어진 deck을 상대방에게 넘겨주면 된다.. 이때부터는 선택의 여지가 없이 번갈아가면서 1개씩 카드를 뽑게된다..

- 참고 -
Normal Nim - 마지막에 take 하는 사람이 이기는 경우..
Misère Nim - 마지막에 take 하는 사람이 지는 경우..


자세한 내용은 여기서..
http://en.wikipedia.org/wiki/Nim


Nim Game에 대한 참고자료..






PS) 근데 Misère 이거 어떻게 발음하는거지?! -_-;;

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

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
Game Theory  (0) 2007.12.19
Misère Nim  (2) 2007.12.16
BSP Tree  (0) 2007.08.28
Catalan Number  (10) 2007.08.12
Multinomial Theorem  (0) 2007.08.04

Comments

  1. philosup 2007.12.16 14:08 Permalink Modify/Delete Reply

    대충 봤을때 미저리 인줄알았는데 아니겠지 ㅋ

Leave a Comment


to Top