창재와 한빛이 돈을 모아 맛있는 바나나를 샀다. 바나나는 n(1 ≤ n ≤ 100)개가 달려 있다. 바나나를 나누기 위해 둘은 새로운 게임 하나를 만들었다.

두 명은 서로 번갈아가며 1 이상 m(1 ≤ m ≤ n) 이하만큼의 바나나를 빼서 자기 쪽에 쌓는다. 그러다가 마지막에 바나나를 가져간 사람은 자신이 쌓아놨던 바나나를 전부 먹고, 상대방은 쌓아놨던 바나나를 다시 원래 위치에 돌려 놓고 게임을 다시 시작한다.

게임을 최대한 공평하게 하기 위해 이전 게임에서 진 사람이 먼저 시작한다. 게임은 바나나가 완전히 없어질 때까지 계속된다. 창재와 한빛은 둘 다 욕심이 많기 때문에 가능한 한 많은 바나나를 자기가 먹으려고 한다.

최적의 전략으로 게임을 할 때, 창재가 먹을 수 있는 바나나는 몇 개일까? 게임이 시작하면 창재가 먼저 바나나를 가져간다고 가정한다.

바나나 게임 timer 1s memory 32MB

바나나 게임 1s 32MB