님게임 변형인데, 비슷한 종류의 변형들이 더러 보인다. 이 문제도 거의 비슷한 문제를 풀었던 것 같은 기억은 있는데.. 뭐였는지가 기억이 안남..
각 파일에서 제거할 수 있는 돌의 개수는, 한칸 왼쪽의 파일과의 돌 개수 차이만큼이다. 그러므로, 인접한 파일들간의 돌의 개수 차이들을 상태로 놓고서 생각하는 것이 편리하다. 상태를 처음 주어진 돌의 개수들 a 대신에 s[i] = a[i] - a[i-1] 로 구한 s로 사용하자. 이런 류의 제약이 있는 문제를 접근하는 요령중 하나다
파일의 개수가 n개라고 하자. n-1번째 파일에서 x개의 돌을 제거한다면, 다음턴에 상대는 n번째 파일에서 똑같이 x개의 돌을 제거할 수 있다. 이 경우에 선후공에는 변화가 없이 오직 s[n-1]만 줄어들게 된다. 결국, s[n-1]은 처음에 얼마였건 간에, 상대를 이기는 데에는 영향이 없다. 그냥 승패에 영향이 없는 값이라는 의미이다. 중요한것은 s[n]이다.
마찬가지로, n-3번째 파일에서 x개의 돌을 제거한다면, 다음턴에 상대는 n-2번째 파일에서 x개의 돌을 제거할수 있다. 선후공은 변화가 없는 상태에서 s[n-3]은 줄어들고, s[n-1]은 늘어나고, s[n-2]와 s[n] 에는 변화가 없다. s[n-1]은 승패에 영향이 없다고 했으니, s[n-3]만 줄어든다. 결국 같은 논리로 s[n-3]도 승패와는 관련 없는 값이다.
이런식으로 의미없는 액션들을 치우고 나면, 의미있는 동작들은 n-2m 번째 파일에서 돌을 제거하는 행동들이다. 이것든 s[n-2m]를 줄이게 된다. 결국 이 게임은 s[n-2m] 들의 값들로만 이루어지는 님게임과 동일한 게임이 된다