백준 9184 재귀함수 + 다이나믹 프로그래밍 + 딕셔너리 - 튜플 키

	result = {}
	def w(a, b, c):
	if (a, b, c) in result.keys():
	return result[(a, b, c)]
	if min(a, b, c) <= 0:
	result[(a, b, c)] = 1
	elif max(a, b, c) > 20:
	result[(a, b, c)] = w(20, 20, 20)
	elif a < b < c:
	result[(a, b, c)] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
	else:
	result[(a, b, c)] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
	return result[(a, b, c)]
	while True:
	a, b, c = map(int, input().split())
	if a == b == c == -1:
	break
	print('w(', a, ', ', b, ', ', c, ') = ', w(a, b, c), sep='')

view raw 백준 9184 신나는 함수 실행 hosted with ❤ by GitHub

재귀함수의 속도를 끌어올리기 위해 한번 계산한 값을 저장하는 메모이제이션이 필요하다. 위와 같이 인자가 3개인 재귀함수는 단순히 리스트의 인덱스로 저장할 수 없기에 딕셔너리와 튜플을 이용해 저장할 수 있다. 딕셔너리는 가변적인 리스트는 키 값으로 가질 수 없지만, 불변 값을 가지는 튜플은 키 값으로 사용한다.