파이썬으로 숫자 줄이기 게임 승자 판별하기: 알고리즘과 구현 예제

문제 소개

아말(Amal)과 비말(Bimal)이 숫자 줄이기 게임을 하고 있다고 가정해 보겠습니다. 두 사람은 하나의 자연수 n을 두고 번갈아 가며 다음 규칙에 따라 수를 줄여 나갑니다.

• 현재 수가 2의 거듭제곱이면 그 수를 2로 나눕니다.
• 현재 수가 2의 거듭제곱이 아니라면, 바로 아래에 있는 2의 거듭제곱만큼 수를 줄입니다.
• 수를 1로 만들면 게임이 끝나며, 승자는 판정 기준에 따라 결정됩니다.
• 아말이 항상 먼저 시작합니다.

예를 들어 입력이 n = 19라면 출력은 Amal이 됩니다.

접근 방법

이 문제는 수를 1까지 줄이는 데 필요한 연산 횟수를 센 뒤, 그 횟수의 홀짝성(짝수/홀수)으로 승자를 판별하는 방식으로 해결할 수 있습니다. 전체 과정은 다음과 같습니다.

1. 연산 횟수를 저장할 변수 res를 0으로 초기화합니다.
2. n이 1보다 큰 동안 다음을 반복합니다.
   • b를 1로 초기화하고, b × 2가 n보다 작은 동안 b를 계속 두 배씩 키워 n 이하에서 가장 큰 2의 거듭제곱을 구합니다.
   • n에서 b를 뺀 뒤, res를 1 증가시킵니다.
3. 반복이 끝난 후 res가 짝수이면 'Amal'을, 그렇지 않으면 'Bimal'을 반환합니다.

파이썬 구현 예제

다음 코드를 통해 더 잘 이해해 보겠습니다.

def solve(n):
   res = 0
   while(n > 1):
      b = 1
      while(b * 2 < n):
         b *= 2
      n -= b
      res += 1
   if res % 2 == 0:
      return 'Amal'
   else:
      return 'Bimal'

n = 19
print(solve(n))

입력

19

출력

Amal

실행 과정 살펴보기

n = 19일 때 코드가 어떻게 동작하는지 단계별로 확인해 보겠습니다.

• 첫 번째 반복: 19 이하에서 가장 큰 2의 거듭제곱은 16입니다. n = 19 − 16 = 3이 되고, res는 1이 됩니다.
• 두 번째 반복: 3 이하에서 가장 큰 2의 거듭제곱은 2입니다. n = 3 − 2 = 1이 되고, res는 2가 됩니다.
• n이 1에 도달했으므로 반복이 종료됩니다. 이 코드의 판정 기준에 따르면 연산 횟수 res가 짝수일 때 Amal이 승자이므로, 최종 결과는 'Amal'입니다.

이 알고리즘은 n을 이진수로 생각했을 때 최상위 비트를 하나씩 제거하거나 오른쪽으로 시프트하는 방식과 유사하게 동작합니다. 내부 반복문 한 번이 O(log n)의 시간이 걸리므로, 전체 시간 복잡도는 대략 O((log n)²) 수준으로 매우 효율적입니다.