게임이론 기본기 익히기1 - 약수 더하기 게임에서 반드시 이기는법

22846번: 인증된 쉬운 게임 (acmicpc.net)

 

모니터에 1이 쓰여있는데, 두 사람이 선공부터 번갈아가며 모니터에 쓰인 수의 약수를 더해간다.

 

이 때 제한 k를 초과한 사람이 패배하게 된다.

 

k가 주어질때, 항상 완벽하게 플레이하는 두 사람중 누가 이길까

 

이런 게임 문제는 보통 1부터 최선의 전략으로 해보면 눈치로 풀면 풀리는 경우가 종종 있더라

 

실제로 해보면 k = 2,6의 경우에만 선공이 이길 수 있고 나머지는 후공이 반드시 이긴다 

 

k = int(input())

if k == 2 or k == 6:
    
    print('Kali')

else:
    
    print('Ringo')

 

 

근데 언제까지 이렇게만 할 수는 없지

 

그리고 이렇게 찾기 힘든 문제도 있더라

 

개념을 확실히 알아야돼

 

1) 상태 정의: 게임에서 '상태'를 정의할 수 있는데, 이 경우 모니터에 쓰인 숫자 i를 상태라고 정의하자

 

두 사람이 게임하고 무승부가 없으니 모든 상태는 선공이 이길 수 있는 상태 or 후공이 이길 수 있는 상태가 된다.

 

두 플레이어가 최선의 플레이를 하므로,

 

현재 상태에서 갈 수 있는 모든 상태가 선공이 이기는 상태라면 현재 상태는 후공이 이기는 상태이고,

 

현재 상태에서 갈 수 있는 모든 상태가 후공이 이기는 상태라면 현재 상태는 선공이 이기는 상태이다.

 

 

2) 상태 변화: i의 약수를 더하여 현재 상태를 변화시킬 수 있다

 

선공이 현재 상태 i에서 시작한다면, 다음 후공은 i + (i의 약수)로 시작하게 된다.

 

그런데 i의 약수가 n개라면 후공에 넘길 수 있는 수는 n개가 된다.

 

3) 승리 전략: 따라서 내가 이길려면, 여러 가능한 수 중 상대가 이길 수 없는 숫자를 전달해야한다.

 

그러므로 i의 약수 중 어떤 약수 하나를 더했을때, 후공이 이길 수 없는 상태라면, 선공이 이길 수 있는 상태가 된다.

 

--------------------------------------------------------------------------------------------------------------------------------------------------------

 

위 개념을 그대로 적용하자

 

1) 상태 정의: dp[i] = 모니터에 쓰인 수가 i일 때, 선공이 이길 수 있으면 1이고 이길 수 없으면 0

 

어떤 과정을 통해 dp를 잘 채우면 1부터 시작하기 때문에 dp[1]이 정답이다.

 

어떤 수 i에 대해 i의 약수를 $O(\sqrt{i})$로 찾아서, 약수 j에 대하여...

 

선공은 후공에 i+j를 넘겨줄 수 있다.

 

2) 승리 전략: 따라서, dp[i+j] = 0인 i+j를 넘겨줘야하고, 그러한 j가 있다면 dp[i] = 1이 된다.

 

즉, dp[i+j] = 0인 상태, 후공이 이기는 상태가 하나라도 발견된다면 현재 상태 dp[i] = 1로 선공이 이기는 상태이다.

 

 

그런데 dp를 채울때, 1부터 시작하면 1보다 큰 수 i+j 상태는 아직 결정된 상태가 아니므로 거꾸로 채워나가야 한다.

 

큰 수부터 거꾸로 채워나가면 작은 수의 경우 약수를 더하면 수가 커지는데, 그 큰 수에 대해서는 이미 상태가 결정되어있으니까  

 

k = int(input())

#dp[i] = i에서 시작했을 때 선공이 이길 수 있는가?
dp = [0]*(k+1)

#현재 사람이 i에서 다음 사람에게 넘길 수 있는 수는 i + (i의 약수)
#무승부가 없으므로 현재 상태는 선공이 이기거나 후공이 이기거나 둘 중 하나
#두 사람이 완벽하게 플레이하므로 선공이 이기는 상태에서 상태변화하면 후공이 이기는 상태
#후공이 이기는 상태에서 상태변화하면 선공이 이기는 상태
#현재 사람이 반드시 이길려면, i+(i의 약수)가 후공이 이길 수 있는 상태여야한다
#약수 j에 대하여 dp[i+j] = 0이면 dp[i] = 1


#1부터 채워나가면, dp[i+j]값은 결정되어있지 않으니 테이블이 채워지지 않는다
#k-1부터 거꾸로 채워나가면 i에 대하여 dp[i+j]는 이미 결정되어있으니 테이블을 채울 수 있다
for i in range(k-1,0,-1):

    for j in range(1,int(i**(1/2))+1):
        
        if i % j == 0:
            
            if i+j <= k and dp[i+j] == 0:
                
                dp[i] = 1
            
            if j*j != i:
                
                if i + i//j <= k and dp[i+i//j] == 0:
                    
                    dp[i] = 1

#dp[1]은 1에서 시작했을때 누가 이겼는지 알려줌
if dp[1] == 1:
    
    print('Kali')

else:
    
    print('Ringo')