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()
ps/problems/boj/7654.txt · 마지막으로 수정됨: 2023/12/13 13:51 저자 teferi
토론