12902 Alice and Bob (백준, python3)

https://www.acmicpc.net/problem/12902

시간 제한	메모리 제한
2초	512MB

문제

Alice와 Bob은 두 명이 할 수 있는 게임을 하나 만들었다. 규칙은 다음과 같다.

1. n개의 서로 다른 자연수로 이루어진 집합을 하나 갖고 시작한다.
2. 두 명은 번갈아서 차례를 가지며, 각자의 차례에 다음과 같은 동작을 수행한다: 집합 내에서 서로 다른 두 자연수 x와 y를 고른다. 단, |x-y|가 집합 내에 존재해서는 안 된다. 이렇게 x와 y를 고른 이후, 그것을 고른 사람이 |x-y|를 집합 내에 넣는 것으로 그 사람의 차례가 종료된다.
3. 더 이상 고를 수 있는 (x,y)가 없는 사람이 패배한다.

두 사람이 모두 최적의 전략으로 플레이할 때, 처음에 주어진 n개의 자연수에 대해 누가 승리하게 될지 출력하시오. 단, 처음 시작하는 사람은 항상 Alice이다.

 

입력

첫 번째 줄에는 처음 집합의 크기 n이 주어진다. (2 ≤ n ≤ 100)
다음 줄에는 n개의 자연수 c₁~c_n이 빈 칸을 사이에 두고 주어진다. (1 ≤ c_i ≤ 109)
모든 c_i는 서로 다름이 보장된다.

 

출력

게임에서 Alice가 승리한다면 “Alice”, Bob이 승리한다면 “Bob”을 출력한다.

 

---

풀이

뭔가 또 엄청 복잡한 것 같지만 게임을 직접 해보면 추가되는 숫자들의 공통점을 알 수 있습니다. 다음 예를 봅시다.

3과 6으로 만들 수 있는 숫자는 없습니다. 3과 8로 만들 수 있는 숫자는 8-3 = 5, 5-3 = 2, 3-2 = 1이 있습니다. 1이 만들어지면 가장 큰 수인 8까지의 모든 자연수를 만들 수 있습니다.

이 경우는 어떨까요? 10-8 = 2로 2를 만들고 나면 10으로부터 4 까지 만들 수 있습니다. 1은 만들 수 없네요.

이번에는 9-6 = 3으로 3을 만들고 나면 15로부터 12까지 만들 수 있습니다. 1, 2는 만들 수 없습니다.

 

만들어지는 가장 작은 수는 집합의 최대공약수입니다. 게임의 과정을 보면 유클리드 호제법과 유사합니다. 실제로 이 과정을 반복해서 만들 수 있는 수들은 모두 집합 최대공약수의 배수들 뿐입니다. 집합의 최대공약수를 구하고 집합의 가장 큰 수까지의 최대공약수의 배수의 개수를 구한 후에 집합의 크기를 빼주면 Alice와 Bob이 게임을 하며 만들 수 있는 숫자의 개수가 나옵니다. 이게 홀수라면 마지막으로 Alice가 숫자를 만들 수 있고, 짝수라면 Bob이 숫자를 만들 수 있습니다.

 

 

정답 코드

import sys
input = sys.stdin.readline
def solution():
    n = int(input())
    c = list(map(int, input().split()))
    def euc(a, b):
        while b != 0:
            a, b = b, a % b
        return a
    k = c[0]
    for i in range(1, n):
        k = euc(k, c[i])
    print("Alice" if (max(c) // k - len(c)) & 1 else "Bob")
solution()