[백준] 9184번 신나는 함수 실행 / 파이썬(python)

# 문제 링크

www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

# Soultion(실패)

단순 재귀를 이용하여 시간초과 문제 발생

def w(a,b,c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
 
    if a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)
 
    if a < b and b < c:
        return w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
 
    else:
        return w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
 
while(1):
    a,b,c = map(int,input().split())
    if a==-1 and b==-1 and c==-1:
        break
    else:
        print(w(a,b,c))
        

 

# Soultion(성공)

튜플을 이용하여 한번 사용한 w(a,b,c)값은 w_li에 저장하여 호출하여 사용

w_li = {} #값 저장
 
def w(a,b,c):
    if (a,b,c) in w_li:
        return w_li[(a,b,c)]
    
    else:
        if a <= 0 or b <= 0 or c <= 0:
            w_li[(a,b,c)] = 1
            return 1
 
        if a > 20 or b > 20 or c > 20:
            w_li[(a,b,c)] = w(20, 20, 20)
            return w(20, 20, 20)
 
        if a < b and b < c:
            w_li[(a,b,c)] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
            return w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
 
        else:
            w_li[(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 w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
 
while(1):
    a,b,c = map(int,input().split())
    if a==-1 and b==-1 and c==-1:
        break
    else:
        print("w(%d, %d, %d) = %d"%(a,b,c,w(a,b,c)))
        

 

1. 이전에 사용한 값을 저장하기 위한 튜플생성

4. 튜플안에 이미 값이 저장되어있으면 재귀함수를 사용하지않고 바로 호출하여 사용

7. 각각의 경우를 계산하여 w_li 튜플에 저장

25. 무한루프를 사용하여 -1 -1 -1이 들어오면 멈추도록 작성