Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬(Python)으로 타워 높이 줄이기 게임의 승자를 찾는 프로그램

문제 소개

height라는 배열이 주어졌다고 가정해 보겠습니다. 배열에는 서로 다른 높이를 가진 n개의 타워가 있으며, Amal과 Bimal 두 플레이어가 아래 규칙에 따라 게임을 진행합니다.

  • 선공: Amal이 항상 먼저 플레이합니다.
  • 규칙: 매 턴 현재 플레이어는 높이가 X인 타워 하나를 선택해 높이를 Y로 줄입니다. 단, 1 ≤ Y < X이며 Y는 X를 나누어떨어지게 하는 값(약수)이어야 합니다.
  • 패배 조건: 더 이상 둘 수 있는 수가 없는 플레이어가 게임에서 패배합니다.

우리의 목표는 이 게임의 승자 이름을 구하는 것입니다.

예를 들어 입력이 height = [3, 1, 2]라고 해보겠습니다. 초기 타워 높이는 {3, 1, 2}이며, Amal이 높이 2짜리 타워를 1로 줄이면 Bimal은 높이 3짜리 타워를 1로 줄일 수 있습니다. 그 시점에 Amal에게는 더 이상 가능한 수가 없으므로 Bimal이 승리합니다.

풀이 접근 방식

이 문제는 조합 게임 이론의 대표격인 님(Nim) 게임 구조를 띠고 있으며, 스프라그-그런디(Sprague–Grundy) 정리를 활용하면 깔끔하게 해결됩니다.

핵심 아이디어는 각 타워의 그런디 값이 해당 높이의 총 소인수 개수(중복 포함)와 같다는 점입니다. 높이 X를 자신의 약수 Y로 줄인다는 행위는 결국 소인수를 하나 이상 제거하는 과정과 같기 때문입니다. 따라서 다음 순서로 문제를 풉니다.

  1. 각 타워 높이를 소인수분해하여 소인수의 총개수를 계산합니다.
  2. 모든 타워의 값을 XOR 연산으로 합산합니다.
  3. XOR 결과가 0이 아니면 선공(Amal), 0이면 후공(Bimal)이 승리합니다.

단계별 알고리즘

  • 배열 a와 길이 n을 인자로 받는 util() 함수를 정의합니다.
  • ans := 0으로 초기화한 뒤, i를 0부터 n-1까지 순회하며 ans := ans XOR a[i]를 수행하고 ans를 반환합니다.
  • 메인 로직에서는 다음을 수행합니다.
    • n := height 배열의 크기
    • b := 크기가 n이고 0으로 채워진 배열 생성
    • i를 0부터 n-1까지 반복:
      • height[i] == 1이면 b[i] := 0
      • 그렇지 않으면 b[i] := 0으로 초기화하고, j := 2, root := √height[i]의 내림값으로 설정합니다. height[i] ≠ 1이면서 j ≤ root인 동안, j가 height[i]의 약수일 때마다 b[i]를 1씩 늘리고 height[i]를 j로 나눕니다. 반복 종료 후에도 height[i] ≠ 1이면 남은 소인수 하나를 위해 b[i] += 1을 수행합니다.
  • ans := util(b, n)
  • ans ≠ 0이면 "Amal", 그렇지 않으면 "Bimal"을 반환합니다.

구현 예제

아래 파이썬 코드를 통해 실제 동작을 확인해 보겠습니다.

def util(a,n):
    ans = 0
    for i in range(n):
        ans = ans^a[i]

    return ans

def solve(height):
    n = len(height)
    b = [0 for i in range(n)]

    for i in range(n):
        if(height[i] == 1):
            b[i] = 0
        else:
            b[i] = 0
            j = 2

            root = int(pow(height[i],0.5))
            while(height[i] != 1 and j<=root):
                if(height[i]%j == 0):
                    while(height[i]%j == 0):
                        b[i] += 1
                        height[i] = height[i]//j

                j += 1

            if(height[i] != 1):
                b[i] += 1

    ans = util(b, n)

    if(ans != 0):
        return "Amal"
    else:
        return "Bimal"

height = [3,1,2]
print(solve(height))

입력

[3, 1, 2]

출력

Bimal

복잡도 및 참고 사항

  • 시간 복잡도: O(n × √M) — M은 타워 높이의 최댓값입니다. 각 높이에 대해 제곱근 범위의 시행 나눗셈으로 소인수 개수를 세기 때문입니다.
  • 공간 복잡도: O(n)
  • solve() 함수는 입력 리스트 height를 직접 수정(in-place)합니다. 원본 데이터를 보존해야 한다면 height[:]처럼 복사본을 인자로 넘겨주는 것이 안전합니다.