백준|9184번|신나는 함수 실행

문제설명

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)

위의 함수를 좀 더 빠르게 수행할 수 있도록 하는 문제입니다.

작동 순서
1. 입력의 크기가 -50부터 50사이지만 어느 한 숫자가 0이하일 경우 무조건 1로 계산할 필요가 없으므로 515151의 3차원 배열을 생성해줍니다.
2. a, b, c를 입력받습니다.
3. 함수를 실행하면서 지금까지 수행한 적이 없는 연산일 경우 그 연산을 수행해서 배열에 저장합니다.
4. 함수를 실행하면서 수행한 적이 있는 연산일 경우 배열에 저장된 값을 가져옵니다.
5. 모든 연산이 끝나면 답을 출력합니다.
6. a, b, c가 -1,-1,-1이 입력되면 식을 종료합니다.

소스코드

import sys
memo = [[[False for _ in range(51)] for _ in range (51)] for _ in range (51)]


def w(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    elif a > 20 or b > 20 or c > 20:
        if not memo[20][20][20]:
            memo[20][20][20] = w(20, 20, 20)
        return memo[20][20][20]
    elif a < b < c:
        if not memo[a][b][c]:
            memo[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
        return memo[a][b][c]
    else:
        if not memo[a][b][c]:
            memo[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 memo[a][b][c]


while True:
    A, B, C = map(int, sys.stdin.readline().split())
    if A == B == C == -1:
        break
    print("w(", A, ", ", B, ", ", C, ") = ", w(A, B, C), sep="")

후기
메모이제이션을 활용하면 쉽게 풀 수 있는 문제였습니다. 처음 문제를 풀 때 배열을 복사하는 과정에서 얕은복사를 하여서 오답이 나왔었는데 깊은 복사를 사용하자 바로 해결되었습니다. 공부할 때 그 둘의 차이를 본적이 있지만 그 차이를 정확하게 몰랐었는데 직접 경험해보니 좀 더 알게 된 것 같습니다.