문제
설명
Alice와 Bob은 게임을 하기로 했다.
게임의 방법은 먼저 두 사람이 양의 정수 N을 정하고, 1로 초기화된 x를 가지고 있다.
게임은 Alice가 먼저 시작하며 서로 번갈아 가면서 자신의 차례에 아래의 작업을 한번씩 한다.
x를 2x 또는 2x+1로 대체한다.
x가 N보다 커졌을 때(초과) 그 작업을 한 사람이 패배한다.
예를 들어 N = 1일 때, Alice 는 2x, 2x+1 둘 중에 어느 것을 선택해도 1을 초과하게 되기 때문에 N = 1일 때는 Bob의 승리이다.
N = 5일 때, Alice가 2x+1을 선택하여 x = 3이 되면 Bob은 어느 것을 선택해도 5를 초과하기 때문에 N = 5일 때는 Alice의 승리이다.
N이 주어질 때, 두 사람이 최선을 다해 게임을 한다면 어떤 사람이 이기게 되는지 출력하는 프로그램을 작성하라.
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 하나의 자연수 N(1 ≤ N ≤ 1018)이 주어진다.
출력
각 테스트 케이스마다 게임의 승자를 출력한다.
예제
입력
5
1
5
7
10
123456789123456789출력
#1 Bob
#2 Alice
#3 Bob
#4 Alice
#5 Bob아이디어
게임이론! 어렵다! 전지전능하신 앨리스와 밥은 이미 N이 주어지자마자 자기의 승패를 안다.
베스킨라빈스 31 필승법과 비슷한데, 덧셈이 아닌 곱셈이다. 다행히도 베스킨라빈스 31 문제를
어떻게 접근하는 지는 안다.
상대가 뭔 짓을 해도 지게 만들면 내가 이긴다. -> 잡으면 무조건 지는 수가 있다 -> 그 수를 넘겨주자
예로 베스킨라빈스31에서 숫자를 최대 3개씩 외칠 수 있고 31을 외치면 지는 게임이라면 필승 법은 30을 마지막으로 외치고 상대에게 넘겨주는 것이다. (30을 받은 상대는 최소 1개는 외쳐야하므로 무조건 진다.)
30을 외치기 위해선 [27,29] 사이의 수를 상대가 마지막으로 외치도록 해야한다. 똑같이 내가 26을 마지막으로 외치고 넘겨주면, 상대는 27 28 29 수 중 하나를 넘겨줄 수 밖에 없고, 모든 경우에도 필승법이 있다.
따라서 30을 외치면 이기는 게임이 이제 26을 외치고 넘겨주면 무조건 이기는 게임이 되었다.
같은 논리로 22를 외치면 이기는 게임, 18, 14, 10, 6, 2를 외치면 이기는 게임이 된다. 혹시 만약에 2명이서 베스킨라빈스 31을 하게된다면 선공을 잡고 무조건 2를 외치는 순간 이길 수 있다는 뜻.
2를 외친 뒤 상대가 어떻게 하든 6을 마지막으로 외치고 -> 10, 14, 18, 22, 26 을 외치면 마지막으로 30을 외치고 끝.
베스킨라빈스에서 각자가 할 수 있는 선택지가 숫자를 3개까지 연달아 부르는 것이었다면
이 문제에서는 2x or 2x+1을 외치는 것이다.
N을 초과한 수를 부르면 패배한다면 첫 필승법은 상대에게 N 이하 (N+1)//2보다 큰 수를 넘겨주는 것이다.
(N+1)//2 를 k라 할때 k 이상 N 이하인 수를 넘겨주기 위해선 2x = k or 2x+1 = k 인 x보다 크고 k 미만인 수를 잡아야한다...
그러한 x를 잡기 위해선 어쩌구저쩌구... 그냥 예제를 보자.
적당히 손으로도 할 수 있으면서, 규칙도 파악가능한 예제로 풀어보자.
ex1.
N = 25
[13-25] 숫자를 받은 사람은 진다. ->
[6-12] 숫자를 받은 사람은 이긴다. ->
[3-5] 숫자를 받은 사람은 진다. ->
[1-2] 숫자는 이긴다.
뒤집어서 쓰면 A를 Alice, B를 Bob이라 할때,
A 1 -> 3
B 3 -> 6 or 7
A 6 -> 13, 7 -> 14 or 15
B -> 패배
ex2. (F는 패배 W는 승리)
N = 26
[14-25] F
[7-13] W
[4-6] F
[2-3] T
[1] F
A 1 -> 2 or 3
B 2or3 -> 4~6 (7은 안준다)
A 4~6 -> 8~13
B 8~13 -> 16~26 (27을 안줌)
A -> 패배
똑똑한 분들은 어떻게 바로바로 잘 일반화하시던데 멍청한 본인은 이렇게 예제를 몇개 풀어보면서 규칙을 찾았다. ㅜ
보이는 규칙대로 구간을 구현하였더니 pass!
구현
for tc in range(1,int(input())+1):
N = int(input())
flag = -1
N//=2
N+= 1
while N > 1:
if flag == -1:
N//=2
else:
N = (N+1)//2
flag *= -1
anw = 'Bob' if flag == -1 else 'Alice'
print(f'#{tc} {anw}')첫 턴인 Alice를 자기 자신이라 생각하고 N//2+1을 잡으면 지는 구간으로 잡으면서
flag가 -1이면 Alice가 지는 구간
flag가 1이면 Alice가 이기는 구간으로 생각하였다.
재밌는 것은 3이 지는 구간이어도 1-2 가 이기는 구간이라
[2-3]이 지는 구간에 정확히 나오는 경우가 아니고서야 엘리스가 다 이긴다.
선공ㅈ망겜이다.
실행
입력
# 궁금해서 N = 1 부터 1001까지 승수를 카운트 해봤다.출력
Alice 승 : Bob 승
659 341선공 ㅈ망겜이 맞다.
느낀 점
일단 혼자 힘으로 풀긴 했지만, 짧고 간단한 문제에 비해 생각하는 시간이 길었다.
유형 개념부터 탄탄하게 공부를 해야할 듯 하다.
