Misère Nim

새로운 이론(알고리즘)을 알게되었을때의 쾌감.. 정말 오랜만이다.. 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에 대한 참고자료..

invalid-file

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