Misère Nim
Problem Solving/Algorithm notes 2007. 12. 16. 01:32
새로운 이론(알고리즘)을 알게되었을때의 쾌감.. 정말 오랜만이다.. 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 이거 어떻게 발음하는거지?! -_-;;
이와 같은 문제를 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 |