이렇게 한쪽방향으로 기물의 위치를 이동시키는 게임들은, 각각의 기물마다 최종 상태까지 이동해야 할 거리 x를 구한다음, 돌이 x개 들어있는 무더기가 있는 님 게임의 변형이라고 변환해서 생각하면 좀더 풀이가 쉬워지는 경우가 많다.
이 게임은 m번 칸에 폰을 집어넣으면 이기므로, m-1번칸에 폰이 있으면 승리포지션이 된다. 패배포지션은 m-1번 칸에 폰을 이동시킬수밖에 없는 포지션인데, 이것은 m-2번칸부터 모든 폰이 빈칸 없이 죽 늘어서 있는 상태이다.
폰 여러개가 붙어있을때, 왼쪽 끝폰을 가장 앞의 빈칸으로 이동하는 행동을 모든 폰이 전부 한칸씩 이동하는 행동이라고 바꿔서 생각해도 무방하다. 그러면 게임 진행도중에 폰의 순서가 변하지 않는다. 그리고 처음 시작했을때 폰의 위치의 순서대로, 가장 오른쪽폰의 최종 위치는 m-2번칸, 오른쪽에서 2번째 폰의 최종 위치는 m-3번칸, … 이런식으로 각 폰의 최종 위치와 이동 거리를 구할수 있다.
그리고 이 관점에서 가능한 행동들을 표현하면, 한개의 폰을 오른쪽으로 한칸 움직이거나, 붙어있는 폰들 여러개를 다같이 한칸 움직일수도 있다.
이제 님게임처럼 바꿔서 생각해보면, 각 폰을 그 폰의 이동거리만큼의 돌을 가진 파일이라고 보면 된다. 가능한 행동은 파일 하나에서 돌 하나를 제거하거나, 돌 갯수가 같은 파일 k개에서 각각 돌 하나씩을 제거하는 것이다.
이 상태에서, 승리 전략을 찾기 위해서 꽤나 고생을 했는데, 풀고 나서 나중에 알고보니 이것은
staircase nim 이라는 이미 알려진 게임었다. staircase nim의 풀이는 돌 갯수가 홀수인 파일들만 모은 뒤, 돌갯수가 같은 파일들의 갯수를 가지고 일반 님 게임으로 변환하는 것이다. 자세한 내용은 링크참고.
이 문제에서는 이 staircase nim의 승패를 찾는것이 아니라, 승리할수 있는 행동의 갯수를 찾는것이 목표이다. 각 행동을 취한 결과가 패배포지션이 되는 행동의 갯수를 세면 되는데, 이것을 무식하게 각각의 결과포지션이 패배포지션이 되는지를 각각 O(n)에 계산하면 총 O(n^2)이 되므로 계산이 불가능하다. 현재 포지션의 그런디수를 구해놓고서, 같은 갯수의 돌을 가진 파일의 갯수가 k개일때, 돌 갯수가 홀수면 파일의 갯수를 k-x 개로 만들어서 그런디수를 0으로 만들수 있는지를 확인하고, 돌 갯수가 짝수면 그보다 하나 더 적은 돌 갯수를 가진 파일수를 x개 늘렸을때 그런디수가 0이 되는지 여부를 확인하는 식으로 처리하면 O(n)에 계산이 가능하다