[파이썬/python] 백준 - 4370 곱셈 게임

문제

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

---

문제 설명

1. 백준이와 동혁이는 곱셈 게임을 한다.
   1. 이 게임은 정수 p에 2~9사이의 숫자 중 하나를 곱하면 되는 게임이다.
   2. p = 1로 시작하고, n을 정한다.
2. 백준이부터 무조건 게임을 시작한다.(번갈아가면서 2~9사이의 수를 곱한다.)
3. 이 때 p ≥ n에 먼저 도달하는 사람이 이기게 된다.
4. 둘 모드 완벽하게 게임을 한다고 가정할 때 이기는 사람이 누구인지 구한다.

 

---

풀이

이 문제는 결국 백준이와 동혁이가 서로 최선의 선택을 반복했을 때 누가 먼저 n에 도달하느냐를 구하는 문제이다.

 

처음 문제를 봤을 때 가장 어려웠던 부분은 최선의 선택이 무엇인지 파악하는 것이었다.

 

그래서 먼저 게임의 흐름을 단계별로 정리했다.

 

우선 게임은 항상 백준이가 선공으로 시작한다.

p = 1에서 시작하고 각 턴마다 2부터 9 사이의 숫자를 곱할 수 있으며, p ≥ n이 되는 순간 그 턴의 플레이어가 승리한다.

 

이 조건을 기준으로 각 라운드에서 누가 이길 수 있는지 범위를 직접 확인해 보면 다음과 같은 패턴이 보인다.

 

1라운드

백준이는 처음 턴에서 p에 2부터 9 사이의 숫자를 곱할 수 있다.

따라서 n ≤ 9라면 백준이가 한 번의 턴으로 바로 p ≥ n을 만들 수 있기 때문에 무조건 승리한다.

 

즉 1 ≤ n ≤ 9 구간에서는 백준이의 승리이다.

 

2라운드

만약 n이 10 이상이라면 백준이는 첫 턴에서 바로 승리할 수 없다.

 

이 경우 백준이는 가능한 한 크게 값을 늘리기 위해 9를 곱한다고 생각할 수 있다.
그러면 p = 9가 되고 다음 턴은 동혁이의 차례가 된다.

 

동혁이는 자신의 턴에서 2부터 9까지의 숫자를 곱할 수 있기 때문에 최대 9 × 2 = 18까지 만들 수 있다.

따라서 10 ≤ n ≤ 18 범위에서는 동혁이가 무조건 승리할 수 있다.

 

3라운드

n이 19 이상이라면 동혁이도 바로 승리할 수 없다.

 

이 경우 다시 백준이의 턴이 오게 되고, 백준이는 다시 가능한 한 크게 값을 늘리기 위해 9를 곱한다고 볼 수 있다.

즉 18 × 9 = 162이 되기 때문에 19 ≤ n ≤ 162 범위에서는 백준이가 승리하게 된다.

 

이와 같은 방식으로 게임의 흐름을 계속 확장해 보면 다음과 같은 패턴이 반복된다.

 

백준이 턴 → p에 9를 곱한다.
동혁이 턴 → p에 2를 곱한다.

 

결국 p는 다음과 같은 형태로 증가한다.

 

1 → 9 → 18 → 162 → 324 → ...

 

따라서 매 단계마다

 

9를 곱했을 때 p ≥ n 이 되면 백준이의 승리
2를 곱했을 때 p ≥ n 이 되면 동혁이의 승리

 

라고 정리할 수 있다.

 

이 과정을 반복하면서 p가 n 이상이 되는 순간을 확인하면 승자를 결정할 수 있다.

 

그래서 p를 1에서 시작해 9와 2를 번갈아 곱하면서 n 이상이 되는 시점을 확인하도록 반복문으로 구현했다.

알고보면 어렵지 않은데 규칙 찾는게 어렵게 느껴진 문제였다..

 

 

 

---

코드

import sys
input = sys.stdin.readline

winner = { 2: 'Donghyuk wins.', 9: 'Baekjoon wins.'}

while True:
    try:
        n = int(input())
    except: 
        exit()

    p = 1
    end = 0

    while not end:
        for i in [9,2]:
            p *= i

            if p >= n:
                print(winner[i])
                end = 1
                break

---

시간복잡도

• 두 명이 한 번 플레이 할 때마다 18배씩 커지게 된다.
• 따라서 $p = 18^k$라고 가정한다면 $p ≥ n$이므로 $18^k ≥ n$이다.
• 양변에 $log_{18}$을 취하게 되면 $k ≥ log_{18}n$ 따라서  $O(logn)$만큼의 시간복잡도를 가지게 된다.
• n은 최악의 경우 4294967295, 약 $2^{32}$이다. 따라서 약 7~8회 정도 실행되기 때문에 $O(1)$에 가깝게 소요되지 않을까 싶다.