[BOJ][Python] 25179 배스킨라빈스~N~귀엽고~깜찍하게~

Overview

• 체감 난이도: ★★☆☆☆
• 문제 레벨: 실버 4
• 문제 유형: 수학, 게임이론
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

이미지 클릭 시 문제로 이동

 

[코드]

이 문제는 2인 게임 필승 전략을 이미 알고 있던 사람이라면 쉽게 풀 수 있다. 

우리가 알고 있는 베스킨라빈스 31 게임과 다른 점은,

1. 플레이어는 2명으로, 첫 번째 플레이어로 고정되어있다. 
2. 숫자는 1부터 시작하며, 마지막 숫자는 입력으로 받는다. ( 1 <= N <= 10^18)
3. 플레이어의 턴에 부를 수 있는 정수의 개수는 M개로, 마찬가지로 입력으로 받는다. ( 1 <= M <= 10^18)

이 게임의 필승 전략은 특정 "패턴"을 만들어서 승리하는 것이다. 

첫 번째 플레이어가 초항부터 시작해서 일정한 간격으로 숫자를 부르면, 상대방은 그 사이의 숫자를 부를 수 밖에 없고, 결국 마지막 숫자들을 첫 번째 플레이어가 부를 수 있게 된다. (단 두 번째 플레이어도 필승 전략을 안다면 예외)

 

일반화 하는 방법은 다음과 같다. 

 

(조건)

- 숫자는 j부터 k까지 있다. (ex. 1 - 31)

- 마지막에 필수로 불러야 하는 최소 개수 (ex. l = 1, 부를 수 있는 최소 숫자 개수는 1개로 고정되어 있음)

1. 전체 숫자 개수를 구한다. (총 개수 = k - j + 1)
2. 실제 사용할 수 있는 숫자의 개수를 구한다. (실제 사용 가능한 숫자 개수 = k - j + 1 - l)
3. 한 라운드에 불리는 숫자 개수 계산(한 라운드 = l + m (최소 + 최대))
   1. 왜 m+l인지??
      1. 상대방이 항상 특정 숫자에 도달하게 만들기 위해
      2. 한 라운드에서 한 플레이어가 상대방에게 승리 가능 상태를 넘길 수 있는 범위를 나타낸다. 
      3. 그 특정 숫자는 m+l 씩 늘어나는 숫자이다. (승리 조건이 주기적으로 반복)
4. 나머지 r 구하기 (사용 가능한 숫자 개수 / 한 라운드 숫자 개수 = 몫 ... 나머지) 
5. 초항 구하기 (j + r - 1)

=> 초항으로부터 한 라운드 숫자 개수씩 더해가며 필승 수열을 만들 수 있다. 

=> 0 < r <= m 이 성립하는지를 확인하면 첫 번째 플레이어의 필승 전략 사용 가능 여부를 알 수 있다. 

 

(예시)

n = 31, m = 3 일 경우, (예제 입력 1) * l 과 j 는 1로 고정되어 있다. 

나머지 r은, (31-1) % (3+1) 로 2이다. 

첫 번째 플레이어가 자신의 턴에서 마지막으로 부르는 숫자가 2, 6, 10, 14, 18, 22, 26, 30 와 같으면 이길 수 있다. 

m = 3 이므로, 첫 턴에 1, 2, 3을 부를 수 있다. 

2까지 부르면 이길 수 있으므로 n = 31, m = 3 인 경우 이길 수 있다. (Can win)

 

 

❓왜 0 < r <= m 인지? 

• r > 0 이어야 하는 이유
  • r = 0 이라는 것은 현재 숫자 상태가 (m+1)의 배수라는 뜻
  • 플레이어가 숫자를 몇 개 부르더라도 상대방이 다시 (m+1)의 배수 상태로 만들 수 있다는 뜻이다. 
    • 즉, 게임의 흐름을 바꿀 수 없는 상태에 놓인다. 
• r <= m 이어야 하는 이유
  • 한 턴에 플레이어가 부를 수 있는 숫자의 최대 개수는 m개이다. 

 

[최종 코드]

n, m = map(int, input().split())
print("Can win" if 0 < (n-1) % (m+1) <= m else "Can't win")