사용자 도구

사이트 도구


ps:problems:boj:7654

Number Game

ps
링크acmicpc.net/…
출처BOJ
문제 번호7654
문제명Number Game
레벨골드 3
분류

게임 이론

시간복잡도O(T)
인풋사이즈T<=?
사용한 언어Python 3.11
제출기록31120KB / 40ms
최고기록40ms
해결날짜2023/12/13

풀이

  • 그냥 평범한 21 game 에서도 후공이 이기기는 매우 어렵다. 처음 시작하는 수가 21의 배수일때만, 후공이 (21 - 선공이 부른 수) 를 계속 부르는 전략으로 이길수 있다. 그런데 랜덤으로 전략을 세워서 이길 생각을 하다니..
  • 후공이 이기는 경우는 결국 N이 21의 배수이고 랜덤으로 뽑은 전략이 우연히 최적 전략이 되는 경우, 즉 a=[20,19,18,..,1]인 경우뿐이다.
  • 이렇게 생각하고 제출했다가 2번 오답을 먹었다.; 기본적으로는 랜덤으로 고른 전략대로 숫자를 부르지만, 자기턴의 숫자가 20 이하면 그 숫자를 그냥 불러서 이긴다는 조건이 하나 더 있다. 이것을 생각하면 N이 21이라면, 후공은 자기 전략과 관계없이 항상 승리할수 있다.
  • 각 케이스마다 들어오는 수의 갯수는 20개로 고정되어있으므로, 그냥 O(1)이라고 생각하면 된다.

코드

"""Solution code for "BOJ 7654. Number Game".

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

Tags: [game thoery]
"""

import sys

END_OF_INPUT = '0'
CANNOT_WIN_STRATEGY = '20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1'


def main():
    while (line := sys.stdin.readline().rstrip()) != END_OF_INPUT:
        N = int(line)
        a = sys.stdin.readline().rstrip()

        cannot_win = (N == 21) or (N % 21 == 0 and a == CANNOT_WIN_STRATEGY)
        print('Carl can\'t win' if cannot_win else 'Carl can win')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
F N G U O
 
ps/problems/boj/7654.txt · 마지막으로 수정됨: 2023/12/13 13:51 저자 teferi