과정
1. defaultdict를 이용해서 값을 저장
2. w함수에서 dic 값이 있으면 그걸 사용, 없으면 w함수를 통해 계산
from collections import defaultdict
basic =0
dic=defaultdict(lambda:basic)
def w(a,b,c):
if dic[(a,b,c)]!=basic:
return dic[(a,b,c)]
if a<=0 or b<=0 or c<=0:
dic[(a,b,c)]=1
return 1
if a>20 or b>20 or c>20:
if dic[(a,b,c)]==basic:
dic[(a,b,c)]=w(20,20,20)
return dic[(a,b,c)]
if a<b and b<c:
if dic[(a,b,c-1)]==basic:
dic[(a,b,c-1)]=w(a, b, c-1)
if dic[(a,b-1,c-1)]==basic:
dic[a,b-1,c-1]=w(a, b-1, c-1)
if dic[(a,b-1,c)]==basic:
dic[(a,b-1,c)]=w(a,b-1,c)
dic[(a,b,c)]=dic[(a,b,c-1)]+dic[(a,b-1,c-1)]-dic[(a,b-1,c)]
return dic[(a,b,c)]
if dic[(a-1, b, c)]==basic:
dic[(a-1, b, c)]=w(a-1, b, c)
if dic[(a-1, b-1, c)]==basic:
dic[(a-1, b-1, c)]=w(a-1, b-1, c)
if dic[(a-1, b, c-1)]==basic:
dic[(a-1, b, c-1)]=w(a-1, b, c-1)
if dic[(a-1, b-1, c-1)]==basic:
dic[(a-1, b-1, c-1)]=w(a-1, b-1, c-1)
dic[(a,b,c)]=dic[(a-1, b, c)]+dic[(a-1, b-1, c)]+dic[(a-1, b, c-1)]-dic[(a-1, b-1, c-1)]
return dic[(a,b,c)]
while True:
a,b,c=map(int,input().split())
if a==-1 and b==-1 and c==-1:
break
print('w(%d, %d, %d) = %d'%(a,b,c,w(a,b,c)))
time:50분
추가사항
굳이 이렇게 defaultdict를 이용하지 않아도 0~20까지의 3차원 dp를 초기화해서 사용해도된다.
또한 if문을 계속해서 쓸 필요없이 dic[(a,b,c)] = w + w - w 이런식으로 둬도 충분히 빠르게 수행된다.
