[BOJ][Pyhon][9184] 신나는 함수 실행

[문제 및 출처]

https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

[어떻게 풀까?]

w(1,1,1) -> w(0,1,1) + w(0,0,1) + w(0,1,0) - w(0,0,0)

나열을 해보면 이런식으로 된다.

w(2,2,2) -> w(1,2,2) + w(1,1,2) + w(1,2,1) - w(1,1,1)

이라? 나는 w(1,1,1)을 알고 있지 않나?

그렇다면 컴퓨터에게도 이것을 알려주면 좀더 쉽고 빠르게 하지 않을까?

반복은 컴퓨터가 훨씬 잘하니까 말이다. 그렇게 된다면 반복되는 구간은 확 줄어들 것이다.

코드를 구현해보면 다음과 같다. 

3차원 배열을 사용하는 아이디어는 여러 블로그에서 찾았다. 나머지 구현은 스스로 해보았다.

[코드]

#일단 구현해보고 짧게 만들 방법을 생각해보자.

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 stack[a][b][c]:  #여기에 있어야 인덱스 에러 방지!
        return stack[a][b][c]
    if a<b and b<c:
        stack[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return stack[a][b][c]
    
    stack[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 stack[a][b][c]

stack = [[[0] * 21 for i in range(21)] for i in range(21)]

while True:
    a, b, c = map(int, input().split())

    if a==-1 and b==-1 and c==-1:
        break
    answer  = w(a, b, c)
    
    print(f"w({a}, {b}, {c}) = {answer}")