백준 9657 돌 게임 3 (Python)

돌 게임 문제는 DP로 쉽게 풀 수 있지만 미니맥스 알고리즘을 사용한 풀이도 가능합니다. 미니맥스 알고리즘 풀이를 찾아봤지만 없어서 직접 구현했습니다.

 

미니맥스 알고리즘은 서로 게임에 최선을 다하는 알고리즘입니다. 나는 상대방에게 이득이 되는 행동을 하지 않고 상대방도 나에게 이득이 되는 행동을 하지 않도록 탐색하는 알고리즘입니다.

 

minimax(stone, player) 함수는 남은 돌의 개수(stone)과 나 또는 상대방인지를 알 수 있는 player 인자를 갖습니다. 마지막 돌을 가져가는 사람이 지는 것이므로 내가 마지막 돌을 가져가면 0(내가 지면), 상대방이 가져가면(내가 이기면) 1을 반환하도록 작성했습니다.

 

이제 내가 돌을 (1 or 3 or 4)개를 가져간 후 상대방의 리턴 값은 0(내가 지는 결과) 또는 1(내가 이기는 결과)일 것입니다. 이때는 내가 이기는 결과를 가져가기 위해 max 함수를 사용합니다. 마찬가지로 나의 리턴 값도 0 또는 1일 것이고 상대방이 이기기 위해 내가 지는 결과를 원하므로 min 함수를 사용합니다.

 

	import sys
	sys.setrecursionlimit(10**6)
	INF=1e9
	memo = {}
	def minimax(stone, player):
	if (player, stone) in memo.keys():
	return memo[(player,stone)]
	if stone==0:
	return 0 if player else 1
	value = -INF if player else INF
	# 서로 최선을 다한다
	if player:
	for i in [1,3,4]:
	if stone-i>=0:
	value=max(value,minimax(stone-i,False))
	else:
	for i in [1,3,4]:
	if stone-i>=0:
	value=min(value,minimax(stone-i,True))
	memo[(player, stone)] = value
	return value
	n = int(input())
	x = minimax(n,True)
	print(('SK' if x else 'CY'))

view raw boj9657.py hosted with ❤ by GitHub