[Python] 12070번 gNumbers (Small) / 12071번 gNumbers (Large)

 

 

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

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

---

 

24/05/21

 

 

스몰과 라지 풀이 방식이 거의 유사해서 같은 글로 적어보려고 한다.

 

---

 

문제 접근 방식:

 

 

문제 설명에 앞서서 편의 상 선공이 지는 포지션을 Cold position, 선공이 이기는 포지션을 Hot position이라고 부르겠다.

 

문제의 내용은 Small문제에 들어가면 wizardrabbit님이 번역해놓은 것이 있으므로 이를 참고해보자.

https://www.acmicpc.net/board/view/143383

 

Small의 경우는 제한이 $N = 1, 000$까지이므로, DP배열을 $1,000$까지 선언하여 DP를 돌리면 된다.

 

이 때 어떤 숫자가 g-number라면, 즉, 각 자리 숫자의 합이 소수가 된다면, 선공이 지는 Cold position이라고 할 수 있다.

 

그게 아니라면, 이 숫자를 소인수분해 하여 Cold position으로 갈 수 있는지 따져보면 된다.(그냥 일반적인 게임 DP를 돌리듯 하면 된다.)

 

Cold position으로 갈 수 있다면 Hot position, 즉, 선공이 이기는 포지션이 되고, 어느 곳이든 Cold position으로 갈 수 없다면 Cold position이 될 것이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 12070번 gNumbers (Small)
# 게임 이론, 소수 판정, DP
'''
구글러들은 숫자와 게임, 특히 숫자 게임에 열광합니다!
두 명의 구글러, 로렌스와 시모어가 'gNumbers'를 기반으로 한 새로운 2인용 게임을 발명했습니다.
숫자는 숫자 자릿수의 합에 1과 그 자체 이외의 양의 제수가 없는 경우에만 gNumber가 됩니다.
(특히 1은 gNumber라는 점에 유의하세요.)

게임은 다음과 같이 작동합니다:
먼저, 게임을 플레이하지 않는 사람이 시작 숫자 N을 선택한 다음,
두 플레이어가 번갈아 가며 게임을 진행합니다.
플레이어의 차례가 되면, 플레이어는 현재 숫자 C가 gNumber인지 확인합니다.
만약 그렇다면 플레이어는 즉시 게임에서 패배합니다.
그렇지 않으면 플레이어는 C의 소인수 P를 선택하고,
P가 더 이상 C의 소인수가 아닐 때까지 계속 C를 P로 나눕니다
(예를 들어 현재 숫자가 72라면,
플레이어는 2를 선택하고 9가 될 때까지 2로 반복해서 나누거나
3을 선택하고 8이 될 때까지 3으로 반복해서 나눌 수 있습니다).
그러면 나눈 결과가 새로운 현재 숫자가 되고 다른 플레이어의 차례가 시작됩니다.

로렌스는 항상 먼저 시작하고 지는 것을 싫어합니다.
숫자 N이 주어졌을 때, 두 플레이어가 최적으로 플레이한다고 가정할 때
어느 플레이어가 이길 것이 확실한지 알려주기를 원합니다.
1 < N ≤ 1000.
접근 방법:
그냥 DP
'''
import sys
input = sys.stdin.readline

DP = [0 for _ in range(1001)]
def is_prime(n):  # n은 2이상이라고 가정
    for i in range(2, int(n**.5)+1):
        if n % i == 0:
            return False
    return True
def digit_sum(n):
    s = 0
    while n // 10 != 0:
        s += (n%10)
        n //= 10
    s += n
    return s
def factorize(n):
    number_li = []
    prime = 2
    while n != 1:
        if n % prime == 0:
            cnt = 0
            while n % prime == 0:
                n //= prime
                cnt += 1
            number_li.append(prime**cnt)
        else:
            prime += 1
    return number_li
for i in range(4, 1001):
    if is_prime(digit_sum(i)):
        continue
    back = factorize(i)
    for j in back:
        if DP[i//j] == 0:
            DP[i] = 1
            break
T = int(input())
for i in range(1, T+1):
    N = int(input())
    if DP[N]:
        print(f'Case #{i}: Laurence')
    else:
        print(f'Case #{i}: Seymour')

---

 

문제 접근 방식:

 

 

Large버전은 $N$의 최대 제한이 $10^{15}$이다. 따라서 바텀업으로 모든 값을 구하기에는 무리가 있다.

 

그래서 탑 다운으로 원하는 값만 구하도록 DP를 구성했고, 수가 크기 때문에 소인수 분해가 느릴 것이 걱정되어, 폴라드 로 구현체를 사용해 소인수 분해를 빠르게 구현하도록 했다.

 

Small과의 차이점은 여기까지고, 그 외의 다른 점들은 모두 같다.

 

여담으로, 텍스트로 통과한 사람이 있어서 조금 놀랐는데, 알고보니 구글 코드잼 문제들은 하나의 데이터 세트에 여러 개의 테스트 케이스를 모두 넣는 형식이라 그게 가능했던 것이다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 12071번 gNumbers (Large)
# 게임 이론, 소수 판정, DP
'''
구글러들은 숫자와 게임, 특히 숫자 게임에 열광합니다!
두 명의 구글러, 로렌스와 시모어가 'gNumbers'를 기반으로 한 새로운 2인용 게임을 발명했습니다.
숫자는 숫자 자릿수의 합에 1과 그 자체 이외의 양의 제수가 없는 경우에만 gNumber가 됩니다.
(특히 1은 gNumber라는 점에 유의하세요.)

게임은 다음과 같이 작동합니다:
먼저, 게임을 플레이하지 않는 사람이 시작 숫자 N을 선택한 다음,
두 플레이어가 번갈아 가며 게임을 진행합니다.
플레이어의 차례가 되면, 플레이어는 현재 숫자 C가 gNumber인지 확인합니다.
만약 그렇다면 플레이어는 즉시 게임에서 패배합니다.
그렇지 않으면 플레이어는 C의 소인수 P를 선택하고,
P가 더 이상 C의 소인수가 아닐 때까지 계속 C를 P로 나눕니다
(예를 들어 현재 숫자가 72라면,
플레이어는 2를 선택하고 9가 될 때까지 2로 반복해서 나누거나
3을 선택하고 8이 될 때까지 3으로 반복해서 나눌 수 있습니다).
그러면 나눈 결과가 새로운 현재 숫자가 되고 다른 플레이어의 차례가 시작됩니다.

로렌스는 항상 먼저 시작하고 지는 것을 싫어합니다.
숫자 N이 주어졌을 때, 두 플레이어가 최적으로 플레이한다고 가정할 때
어느 플레이어가 이길 것이 확실한지 알려주기를 원합니다.
1 < N ≤ 10^15.
접근 방법:
그냥 DP, 근데 탑다운
'''
import sys
input = sys.stdin.readline

DP = dict()
DP[1] = 0
def is_prime(n):  # n은 2이상이라고 가정
    for i in range(2, int(n**.5)+1):
        if n % i == 0:
            return False
    return True
def digit_sum(n):
    s = 0
    while n // 10 != 0:
        s += (n%10)
        n //= 10
    s += n
    return s
from random import randrange
from math import gcd
def Miller_Rabin_primality_test(N, a, s, d):
    if a >= N: a %= N
    if a <= 1: return True
    k = pow(a, d, N)
    if k == 1 or k == N-1: return True
    for r in range(1, s):
        k = pow(k, 2, N)
        if k == N-1: return True
    return False
def is_prime_with_Miller_Rabin(N):
    if N == 2: return True
    if N == 1 or N % 2 == 0: return False
    s, d = 0, N-1
    while d % 2 == 0:
        d //= 2
        s += 1
    if N < 4759123141:
        A = [2, 6, 61]
        for a in A:
            if not Miller_Rabin_primality_test(N, a, s, d):
                return False
        return True
    A = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
    for a in A:
        if not Miller_Rabin_primality_test(N, a, s, d):
            return False
    return True
def rho(n): # n의 약수를 구한다
    if is_prime_with_Miller_Rabin(n): return n
    if n == 1: return 1
    if n%2 == 0: return 2
    tortoise, c, d = randrange(2, n), randrange(1, n), 1
    hare = tortoise
    while d == 1:
        tortoise = ((tortoise**2 % n) + c)%n
        hare = ((hare**2 % n) + c)%n
        hare = ((hare**2 % n) + c)%n
        d = gcd(abs(tortoise - hare), n)
        if d == n: return rho(n)
    if is_prime_with_Miller_Rabin(n): return d
    else: return rho(d)
def factorization_with_Pollard_rho(N):
    fac = []
    while N > 1:
        d = rho(N)
        fac.append(d)
        N //= d
    fac.sort()
    dic = dict()
    for i in fac:
        if i not in dic:
            dic[i] = 1
        else:
            dic[i] += 1
    return dic
def top_down(N):
    if N in DP:
        return DP[N]
    if is_prime(digit_sum(N)):
        DP[N] = 0
        return
    dic = factorization_with_Pollard_rho(N)
    for prime, value in dic.items():
        k = N//(prime**value)
        if k not in DP:
            top_down(k)
        if DP[k] == 0:
            DP[N] = 1
            return
    DP[N] = 0
    return
T = int(input())
for i in range(1, T+1):
    N = int(input())
    top_down(N)
    if DP[N]:
        print(f'Case #{i}: Laurence')
    else:
        print(f'Case #{i}: Seymour')