통나무 자르기

풀이

어떻게 풀지 전체를 다 뒤지는 방식으로 해야하나? 하다가 N이 10^9 까지 있어서 전체를 다 뒤지는 방식이면, 2중 for문으로는 해결되지 않을 것이라 생각되었기에 테스트 케이스를 관찰했다.

감이와서 시도해보니 PASS되었다.
먼저 시도하는 사람이 Alice이므로 N이 짝수이면, Alice가 이기고, 홀수라면 Bob이 이기는 게임이된다.

먼저 마지막 2를 손대는 사람이 이기는데, 그게 짝수일 때는 처음 손 댄사람, 홀수일 때는 뒤에 손 댄 사람 이기 때문이다.

따라서 아래처럼 풀었다.

T = int(input())
people = ["Alice", "Bob"]
for testcase in range(1, T+1):
    N = int(input())
    if N %2 == 0:
        print(f'#{testcase} Alice')
    else:
        print(f'#{testcase} Bob')