사용자 도구

사이트 도구


ps:problems:boj:4148

31게임

ps
링크acmicpc.net/…
출처BOJ
문제 번호4148
문제명31게임
레벨골드 3
분류

게임 이론

시간복잡도O(n*m^n + t)
인풋사이즈t<=?, n<=6, m<=4, t
사용한 언어Python 3.11
제출기록34196KB / 80ms
최고기록76ms
해결날짜2023/07/21

풀이

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

코드

"""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()

토론

댓글을 입력하세요:
Y K D᠎ L T
 
ps/problems/boj/4148.txt · 마지막으로 수정됨: 2023/07/21 14:52 저자 teferi