필승 전략 게임 - 베스킨라빈스 31 게임에서 반드시 이길 수 있을까?

1. 베스킨라빈스 31

 

술게임에서 많이 하는 게임이다. 규칙은 다음과 같다.

 

두 사람이 게임을 하는데 1부터 시작해서 3개까지 숫자를 부를 수 있고

 

31을 먼저 부르면 지는 게임이다.

 

예를 들어 A가 1,2,3을 부르면 B는 4,5를 부르고 A는 다시 6,7을 부르고....

 

상대방이 나한테 선공을 양보했다.

 

술을 못마시는 나는 최대로 집중해서 이 게임에서 반드시 이기고 싶다.

 

어떻게 해야 내가 이 게임에서 반드시 이길 수 있을까?

 

 

2. 게임의 필승 전략1

 

결국 내가 게임을 이길려면 마지막에 30을 불러야 게임에서 이길 수 있게 된다.

 

그 전에 내가 불러야 하는 숫자는 얼마일까?

 

상대방이 27, 28, 29중 하나로 끝을 내야 내가 마지막에 30을 부를 수 있다

 

상대방이 27, 28, 29중 하나로 끝을 내게 만들려면 나는 26을 불러야한다.

 

그러면 계속해서, 내가 26을 부를려면 상대방이 몇을 불러야할까?

 

23, 24, 25중 하나를 불러야 내가 26을 부를 수 있게 된다.

 

그러면 상대방이 23, 24, 25중 하나를 부르게 할려면? 나는 22를 불러야한다.

 

이런식으로 반복한다면... 매 순간 내가 불러야하는 수는..

 

30, 26, 22, 18, 14, 10, 6, 2

 

따라서 처음에 내가 1, 2를 부른다면 나는 이 게임에서 반드시 이길 수 있다.

 

 

3. 연습문제

 

20004번: 베스킨라빈스 31 (acmicpc.net)

20004번: 베스킨라빈스 31

 

4. 풀이

 

조금 더 응용해서, 1부터 N개 이하의 수를 부를 수 있다고 할 때, 후공인 내가 이길 수 있는 모든 N을 구해야하는 문제

 

위 사고 과정을 조금 응용해서..

 

선공인 사람이 30을 부르면 이길 수 있으므로,

 

30, 30-(N+1), 30-2*(N+1), ...을 부르면 선공인 사람이 게임에서 이길 수 있다.

 

예를 들어 N = 3라고 한다면..

 

30, 26, 22, 18, 14, 10, 6, 2를 부르면 게임에서 이길 수 있다.

 

따라서 선공인 사람이 최선의 전략으로 게임한다면 처음에 2를 부르면 게임에서 절대로 이길 수 없다.

 

그런데 예를 들어 N = 4라고 한다면..

 

30, 25, 20, 15, 10, 5, 0을 부르면 선공인 사람이 게임에서 이길 수 있다.

 

그런데 부를 수 있는 수는 1부터 시작하는데 처음에 부를 수 있는 수는 1,2,3,4까지 이다.

 

그러니까 5를 부를수가 없다. 

 

이런 경우에는 최선의 전략으로 게임하는 두명에 대해 선공인 사람은 게임에서 이길 수가 없다.

 

후공이 5,10,15,20,25,30을 부를 수 있기 때문이다.

 

그러므로 30부터 (N+1)을 반복적으로 뺄때, 음수가 된 순간 다시 N+1을 더해본다.

 

그리고 얻은 수가 N보다 크다면 후공인 사람이 반드시 이길 수 있고, N보다 작거나 같다면 선공인 사람이 게임에서 이길 수 있다.

 

from sys import stdin

A = int(stdin.readline())

for n in range(1,A+1):
    
    x = 30

    while x > 0:
        
        x -= (n+1)
    
    x += (n+1)

    if x > n:
        
        print(n)

 

 

5. 베스킨라빈스 N

 

조금 더 일반적인 상황으로 확장해보자.

 

이번엔 N을 부르면 게임에서 진다.

 

그런데 부를 수 있는 수는 1부터 X 이하까지이다.

 

선공인 내가 최대로 집중하면 게임에서 반드시 이길 수 있을까?

 

그럴려면 처음에 어떤 수를 불러야할까?

 

 

6. 게임의 필승 전략2

 

그냥 N = 31을 N으로 바꿨을 뿐이고, X = 3을 X로 바꿨을 뿐이다.

 

마찬가지의 사고과정으로 전개해보자.

 

선공인 내가 게임에서 이길려면 N-1을 불러야한다.

 

계속해서 상대방은 N-2, N-3, ...  , N-1-X 중 하나를 불러야 내가 N-1을 부를 수 있다.

 

그렇게 만들려면 그 전에 나는 N-1-(X+1)을 불러야한다.

 

반복적으로 이 게임에서 내가 반드시 이길려면...

 

N-1, N-1-(X+1), N-1-2*(X+1), ...을 불러야 게임에서 이길 수 있다.

 

베스킨라빈스 31게임에서는 N = 31이고 X = 3으로 이 경우 선공인 사람이 반드시 이길 수 있다.

 

하지만 N = 31이고 X를 임의의 수로 만드는 순간 위 문제에서도 알 수 있듯이 선공이 반드시 이기라는 보장이 없다.

 

마찬가지로 N과 X로 일반적으로 확장하는 순간 선공인 사람이 반드시 이기라는 보장은 없다.

 

 

7. 연습문제

 

25179번: 배스킨라빈스~N~귀엽고~깜찍하게~ (acmicpc.net)

25179번: 배스킨라빈스~N~귀엽고~깜찍하게~

 

8. 풀이

 

N, M으로 확장한 베스킨라빈스 게임인데,

 

선공인 사람이 필승하는지 여부를 아는 방법으로

 

N-1, N-1-(M+1), N-1-2*(M+1),....을 구해봐서 이 안의 수를 부를 수 있는지를 체크해야한다고 했는데

 

즉, N-1에서 (M+1)을 반복적으로 빼서 음수가 되는 순간 M+1을 한번 더하고 그 수가 M보다 크다면 후공이 이기고

 

M보다 작거나 같다면 선공이 이기게 된다.

 

그런데  N과 M의 범위가 $10^{18}$으로 매우 크다.

 

최악의 경우 N이 $10^{18}$이고 M = 1이면 이렇게 반복적으로 빼다가는 1초안에 푸는건 절대로 불가능

 

사실 이를 극복하는 테크닉을 이미 배운적이 있다

 

https://deepdata.tistory.com/380

매우 큰 수를 나머지 연산으로 줄일 수 있는 마법(백준-개미)

 

https://deepdata.tistory.com/524

100번할 것을 1번만에 하는 나눗셈 연산 -시험 감독-

 

반복적으로 빼는 대신에 나눗셈 연산 단 1번으로 이를 해결할 수 있다

 

구체적으로 N-1을 M+1로 나눈 나머지가 0이라면.. 게임을 이기기 위해 불러야하는 매직 넘버는

 

0, M+1, (M+2), ...로 시작하고

 

나머지가 r = 1~M이라면 게임을 이기기 위해 불러야하는 매직 넘버가

 

r, r+(M+1), ...

 

그러므로 선공인 내가 이길 수 있는지 알고 싶다면.. N-1을 M+1로 나눈 나머지를 구해서 0이라면 내가 이길 수 없고,

 

0이 아니라면 내가 이길 수 있으며, 선공에 그 나머지만큼을 부르면 된다.

 

from sys import stdin

n,m = map(int,stdin.readline().split())

if (n-1)%(m+1) >= 1:
    
    print("Can win")

else:
    
    print("Can't win")