게임이론 기본기 익히기2 - 2~9 사이 정수 곱하기 게임에서 이기는법

4370번: 곱셈 게임 (acmicpc.net)

 

 

1 < n < 4294967295 사이의 어떤 n에 대하여 1부터 시작해서 2~9 사이의 어떤 정수중 하나를 곱해나간다.

 

p >= n에 먼저 도달하는 사람이 이길 때, 두 사람이 완벽하게 게임한다면 n에 대하여 선공과 후공중 누가 이길까?

 

 

1. 다이나믹 프로그래밍

 

n의 제한이 너무 크기때문에 dp배열을 초기화해서 해결하기는 어렵다

 

그래서 dict를 이용해서 배열의 크기는 잡지말고 필요한 값만 저장하도록 하는 dp를 이용

 

현재 상태가 p라고 한다면, 이 게임은 i = 2,3,..,9중 하나를 곱해서 상태를 변화시킬 수 있고

 

이기거나 지거나 둘중 하나이고 완벽하게 게임하므로

 

현재 이기는 상태라면 상태 변화를 통해 상대가 지는 상태가 되는거고

 

현재 지는 상태라면, 상태 변화를 통해 상대가 이기는 상태가 된다

 

p = 1부터 시작해서 재귀적으로 모든 i = 2,3,4,..,9에 대해 곱한 값 p * i를 조사해서

 

상대가 지게되는 경우가 하나라도 있다면, 해당 p는 반드시 이길 수 있는 상태이다.

 

def game(p):
    
    dp[p] = 0
    
    for i in range(2,10):
        
        if game(p*i) == 0:
            
            dp[p] = 1
            break
    
    return dp[p]

 

 

만약 p >= n이 된다면... 현재 유저는 지는 상태가 된다.

 

p >= n이면 이기는건데 왜 지는 상태가 되는거?

 

n은 1 < n < 4294967295이며, 첫 시작은 1이기 때문에 처음에는 반드시 p < n이다.

 

그러다보니 p >= n이 되는 상태는 게임이 진행된 상태이다.

 

여기서 p*i를 통해 상태를 받아오므로, 받아온 상태 p >= n이 된다면 내가 이기는게 아니고,

 

넘겨준 사람이 이기는것이기 때문에 0을 return해야함

 

이게 좀 어렵네 흐름을 생각하면서 로직을 짜야된다

 

def game(p):
    
    if p >= n:
        
        return 0
        
    dp[p] = 0
    
    for i in range(2,10):
        
        if game(p*i) == 0:
            
            dp[p] = 1
            break
    
    return dp[p]

 

 

마지막으로 n이 매우 크고, 많은 상태를 방문하기 때문에 중복된 계산을 피해줘야한다.

 

이미 계산된 dp값이 있다면 바로 return하도록

 

def game(p):
    
    if dp.get(p,-1) != -1:
        
        return dp[p]
        
    if p >= n:
        
        return 0
        
    dp[p] = 0
    
    for i in range(2,10):
        
        if game(p*i) == 0:
            
            dp[p] = 1
            break
    
    return dp[p]

 

 

2. 게임 이론적 접근

 

n에서 거꾸로 채워나간다고 생각해보자.

 

p >= n이 되는 상태면 게임을 이기므로, 반드시 게임을 이길 수 있는 상태들의 집합은 무엇일까?

 

A = [ceil(n//9), ceil(n//9)+1, ceil(n//9)+2, ... , n-1]이다.

 

이 수들의 집합에서 아무 수를 고르더라도, 2~9중 하나를 곱하면 반드시 p >= n이 되기 때문에..

 

이 상태들의 집합에 도달하는 사람은 반드시 이길 수 있다.

 

예를 들어 n = 162라면 [18,19,20,21,...,161]중 하나에 먼저 도달하면 반드시 이길 수 있게 된다.(win position)

 

 

그러면 A에 도달하기 전의 플레이어, 반드시 지는 플레이어는 어떤 상태에 있게 될까?(lose position)

 

즉 어떤 상태에 있어야, 반드시 A에 도달하게 될까?

 

B = [ceil(ceil(n//9)//2), ceil(ceil(n//9)//2) + 1, ... , ceil(n//9)-1]이다.

 

플레이어는 최소한 2는 곱해야하기 때문에, B 집합에 있는 사람은 싫어도 무조건 A에 도달할 수밖에 없다.

 

 

그러므로

 

1) position = 0일때, n을 9로 나눠서 이기는 포지션을 구한다(승리 상태)

 

2) 그 몫을 n으로 갱신하고 position = 1로 변경

 

3) position = 1이면 n을 2로 나눠서 지는 포지션을 구한다(패배 상태)

 

4) 그 몫을 n으로 갱신하고 position = 0으로 변경

 

5) n이 1이 될때까지 반복한다.

 

 

반복문을 탈출하고 position = 0이라면?

 

position = 1에서, n//2, n%2를 계산하며 n = x로 넘긴 값이 n = 1이라는 의미이므로, 선공이 지는 상태이다.

 

즉, 선공은 시작하면 position = 1(패배상태)로 이동한다는거지

 

position = 1이라면?

 

position = 0에서 n//9, n%9를 계산하며 n = x로 넘긴 값이 n = 1이라는 의미이므로, 선공이 이기는 상태이다.

 

즉 선공은 시작하면 position = 0(승리상태)로 이동한다는 거지

 

def game(n):

    position = 0

    #n부터 거꾸로 시작해서 반드시 이길려면
    #X = [n//9,n//9+1,...,n-1]

    #다음 사람이 X로 보낼수밖에 없는 위치는...(패배하는 위치)
    #Y = [n//9//2, n//9//2+1,..., n//9-1]

    while n > 1:

        if position == 0: #승리 상태

            x,y = n//9, n%9
            position = 1

        else: #패배 상태

            x,y = n//2, n%2
            position = 0

        if y != 0:

            x += 1

        n = x
    
    #n이 1인 순간 position이 0이라면?
    #position = 1에서 n//2,n%2를 계산하고 n = x로 넘긴 다음 position = 0으로 되었으므로
    #이 n은 패배 상태에 속한다는 의미
    if position == 0:

        return 'Donghyuk wins.'

    else:

        return 'Baekjoon wins.'

while 1:
    
    try:

        n = int(input())

        print(game(n))
        
    except:
        
        break