n개의 구슬이 있고 각 라운드에서 플레이어가 양의 제곱 개수의 구슬을 가져와야 하는 2인 게임을 한다고 가정합니다. 플레이어가 해당 제곱 수의 구슬을 가져갈 수 없으면 패배합니다. 따라서 숫자 n이 주어지면 게임에서 이길 수 있는지 여부를 알아내야 합니다. 우리는 항상 첫 번째 턴을 만들고 최적의 구슬 수를 선택합니다.
따라서 입력이 14와 같으면 출력은 True가 됩니다. 첫 번째 턴에서 9개의 구슬을 가져오기 때문입니다. 그러면 다른 플레이어가 최대 4개의 구슬을 가져갈 수 있는 5개의 구슬이 남고 1개의 구슬이 남습니다. 그래서, 다음 턴에서, 우리는 상대방이 움직일 수 없는 0개의 구슬을 뒤에 남겨둔 마지막 구슬을 가져갑니다. 따라서 우리가 이깁니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- n <=0이면
- 거짓을 반환
- ans :=거짓
- (n)의 제곱근) 범위의 i에 대해 -1, 1 감소, do
- i * i> n이면
- 루프에서 나오다
- ans :=ans OR (해결되지 않음(n - i * i))
- as가 참이면
- 반환
- i * i> n이면
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from math import sqrt def solve(n): if n <= 0: return False ans = False for i in range(int(sqrt(n)), 0, -1): if i * i > n: break ans = ans | (not solve(n - i * i)) if ans: return ans return ans print(solve(14))
입력
14
출력
True