메모 딕셔너리로 이미 계산된 w(a,b,c) 결과를 캐싱해 중복 호출을 방지!
def w(a, b, c, memo={}):
if (a, b, c) in memo:
return memo[(a, b, c)]
if a <= 0 or b <= 0 or c <= 0:
return 1
if a > 20 or b > 20 or c > 20:
memo[(a, b, c)] = w(20, 20, 20, memo)
return memo[(a, b, c)]
if a < b and b < c:
memo[(a, b, c)] = w(a, b, c-1, memo) + w(a, b-1, c-1, memo) - w(a, b-1, c, memo)
return memo[(a, b, c)]
memo[(a, b, c)] = w(a-1, b, c, memo) + w(a-1, b-1, c, memo) + w(a-1, b, c-1, memo) - w(a-1, b-1, c-1, memo)
return memo[(a, b, c)]
while True:
line = list(map(int, input().split()))
a, b, c = line[0], line[1], line[2]
if a == -1 and b == -1 and c == -1:
break
print(f"w({a}, {b}, {c}) = {w(a, b, c)}")
