99클럽 코테 스터디 12일차 TIL

 

오늘의 공부 키워드

• 1025 Divisor Game

1025 Divisor Game

디바이저 게임에서는 앨리스와 밥이 차례로 게임을 합니다. 게임 규칙은 다음과 같습니다:

1. 게임은 숫자 nnn으로 시작합니다. 앨리스가 먼저 시작합니다.
2. 각 턴마다 플레이어는 0<x<n0 < x < n0<x<n이면서 n%x==0n \% x == 0n%x==0인 숫자 xxx를 선택해야 합니다. (즉, xxx는 nnn의 약수여야 합니다.)
3. 선택한 숫자 xxx를 nnn에서 빼고, 새로운 nnn값으로 바꿉니다.
4. 더 이상 움직일 수 없는 플레이어가 게임에서 집니다.

목표

게임이 시작할 때 n이 주어졌을 때, 앨리스가 이길 수 있는지 여부를 판단해야 합니다. (두 플레이어 모두 최적으로 게임을 한다고 가정합니다.)

핵심 통찰

게임의 결과는 숫자 n이 짝수인지 홀수인지에 따라 달라집니다:

• n이 짝수일 때, 앨리스는 항상 밥에게 홀수를 남기도록 만들 수 있습니다. 모든 짝수는 최소 하나의 약수(1)를 가지기 때문에, 앨리스는 항상 움직일 수 있습니다.
• n이 홀수일 때, 앨리스가 어떤 움직임을 하든 밥에게 짝수를 남기게 됩니다. 이 경우 밥이 유리하게 됩니다.

따라서, nnn이 짝수로 시작하면 앨리스가 이기고, 홀수로 시작하면 밥이 이깁니다.

예시

• 예시 1:
  • 입력: n=2
  • 앨리스는 1을 선택합니다 (2의 약수).
  • nnn은 2−1=1 이 됩니다.
  • 밥은 더 이상 움직일 수 없기 때문에 앨리스가 이깁니다.
  • 출력: true
• 예시 2:
  • 입력: n=3
  • 앨리스는 1을 선택합니다 (3의 약수).
  • nnn은 3−1 = 2 가 됩니다.
  • 밥은 1을 선택합니다 (2의 약수).
  • nnn은 2−1=1 이 됩니다.
  • 앨리스는 더 이상 움직일 수 없기 때문에 밥이 이깁니다.
  • 출력: false

해결 방법

앨리스가 이길 수 있는지 확인하려면 n 이 짝수인지 홀수인지 확인하면 됩니다.

 

코드

def divisor_game(n: int) -> bool:
    return n % 2 == 0

# 예시로 함수 테스트
print(divisor_game(2))  # 출력: True
print(divisor_game(3))  # 출력: False

 

설명

1. 함수 정의: divisor_game이라는 함수를 정의하고, 정수 n을 입력으로 받습니다.
2. 짝수/홀수 확인: 나머지 연산자 %를 사용하여 nnn이 짝수인지 확인합니다. 만약 n%2==0이면 n은 짝수이고, 함수는 true를 반환합니다. 그렇지 않으면 false를 반환합니다.

이 해결 방법은 주어진 범위 1≤n≤1000내의 어떤 n에 대해서도 효율적으로 작동합니다.

 

 

 

오늘의 회고

 

• 부족함을 느끼지만 실력을 늘리는것이 제일 빠른길임을 명심하자
• 재미있는 문제여서 풀기 좋았다.