99클럽 코테 스터디 11일차 1025. Divisor Game

문제: Divisor Game (약수 게임)

https://leetcode.com/problems/divisor-game/description/

 

설명:

Alice와 Bob는 게임을 하고 있습니다. 게임의 규칙은 다음과 같습니다:

1. Alice와 Bob은 서로 번갈아 가며 숫자 N을 가지고 게임을 시작합니다. Alice가 먼저 시작합니다.
2. 턴마다 현재 숫자 N에서 1부터 N-1까지의 양의 정수 x 중에서 N % x == 0을 만족하는 x를 선택해야 합니다.
3. 선택한 x를 N에서 빼서 새로운 숫자 N - x로 만듭니다.
4. 새로운 숫자 N - x를 가지고 다음 플레이어가 자신의 턴을 진행합니다.
5. 어떤 플레이어가 더 이상 유효한 움직임을 할 수 없는 경우, 그 플레이어는 패배합니다.

주어진 숫자 N이 주어졌을 때, Alice가 게임에서 이기는지 여부를 반환하세요. Alice가 이길 수 있으면 true, 아니면 false를 반환합니다.

 

 

 

 

이 문제는 게임 이론과 관련된 문제로, 특정 수 N에 대해 Alice가 이길 수 있는지 여부를 결정하는 규칙을 찾으면 쉬운 문제였다.

이 규칙을 찾기 위해 여러 값들을 테스트하여 패턴을 찾아볼 수 있다.

규칙 분석

1. N = 1: Alice는 움직일 수 있는 수가 없기 때문에 바로 패배False
2. N = 2: Alice는 1을 빼고 Bob에게 N = 1을 남길 수 있음. Bob은 패배True
3. N = 3: Alice는 1을 빼고 Bob에게 N = 2를 남길 수 있음. N = 2에서는 Bob이 승리하므로 Alice는 패배False
4. N = 4: Alice는 1을 빼고 Bob에게 N = 3을 남길 수 있음. Bob은 N = 3에서 패배하므로 Alice는 승리True

이 패턴을 통해 짝수와 홀수에 따라 게임의 결과가 달라짐을 알 수 있다.

• 짝수 N: Alice가 첫 번째로 움직이고, Bob에게 홀수를 남길 수 있다. 이후, Alice는 항상 짝수를 남겨 게임을 승리할 수 있다.
• 홀수 N: Alice가 첫 번째로 움직이고, Bob에게 짝수를 남길 수 있다. 이후, Bob은 동일한 전략으로 Alice에게 홀수를 남겨 Alice는 패배한다.

따라서, N이 짝수이면 Alice는 이기고, N이 홀수이면 Alice는 진다.

 

def divisorGame(N):
	# 불리언 이용하여 짝수면 True, 홀수면 False 반환
	return N% 2 == 0