[파이썬] 백준 9184 신나는 함수 실행

< 처음 풀이 >

그냥 실행하면 시간 초과가 난다는 것은 알았지만 어떤 식으로 해결 해야 할 지 알지 못했다.

 

< 해결 방법> 

삼차원 리스트를 만들어서 해결을 했다. 중간중간 헷갈리는 부분이 있어 답을 참고하여서 코딩을 하였다. 전체적인 구조는 이해가 간다.

 

import sys
 
# if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
#     1
 
# if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
#     w(20, 20, 20)
 
# if a < b and b < c, then w(a, b, c) returns:
#     w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
 
# otherwise it returns:
#     w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
 
k = [[[0]*(21) for _ in range(21)] for _ in range(21)]
 
 
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 k[a][b][c]:
        return k[a][b][c]
 
    if a < b and b < c:
        k[a][b][c]=w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return k[a][b][c]
 
    k[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 k[a][b][c]
 
while True:
    a,b,c = map(int,sys.stdin.readline().rstrip().split(" "))
    if a==-1 and b==-1 and c==-1:
        break
    else:
        print(f'w({a}, {b}, {c}) = {w(a,b,c)}')