====== 31게임 ======

===== 풀이 =====
  * 간단한 임파셜 게임. 남은 카드들의 갯수가 포지션이 되므로 총 4^6개의 포지션이 있고, 이는 DP를 이용해서 승패를 구하기에 충분한 크기이다.
  * 각 카드별로 남은 갯수를 길이 6짜리 튜플로 표현하면 간단하다. 
    * 2비트씩 할당해서 12비트의 비트마스크를 쓰면 더 효율적이지만, 구현이 번거로워서 그냥 튜플을 사용.
  * bottom-up dp를 사용하자니, 최종포지션부터 이전포지션 순서로 이터레이션하는것이 번거로워서, 그냥 top-down으로 구현했다.
  * 상태별로 승패를 모두 구하는 시간복잡도는 4^6개의 포지션 * 6개의 행동 = 6*4^6이 된다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 4148. 31게임".

- Problem link: https://www.acmicpc.net/problem/4148
- Solution link: http://www.teferi.net/ps/problems/boj/4148

Tags: [game theory]
"""

import functools
import sys


@functools.cache
def is_win_pos(used, card_sum):
    for i in range(1, 7):
        if card_sum + i <= 31 and used[i] < 4:
            used_list = list(used)
            used_list[i] += 1
            if not is_win_pos(tuple(used_list), card_sum + i):
                return True
    return False


def main():
    for inp in sys.stdin:
        inp = inp.rstrip()
        used = [0] * 7
        card_sum = 0
        for c in inp:
            used[int(c)] += 1
            card_sum += int(c)
        player, opponent = ('A', 'B') if len(inp) % 2 == 0 else ('B', 'A')
        print(inp, player if is_win_pos(tuple(used), card_sum) else opponent)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_3}}