problem-9184

유성·2022년 11월 10일
0

PS

목록 보기
15/47

과정
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 이런식으로 둬도 충분히 빠르게 수행된다.

profile
기록

0개의 댓글