새로운 이론(알고리즘)을 알게되었을때의 쾌감.. 정말 오랜만이다.. 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' 카테고리의 다른 글

Ellipse (타원)  (0) 2009.04.15
Combination 개수 구하기 (Pascal's Triangle)  (2) 2009.02.07
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
BSP Tree  (0) 2007.08.28
Catalan Number  (10) 2007.08.12
Multinomial Theorem  (0) 2007.08.04

to Top