BOJ 9148 신나는 함수 실행 Python

https://www.acmicpc.net/problem/9184
DP문제

문제 코드

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. a, b, c 중 한 개라도 0이하면 1을 반환
2. a, b, c 중 한 개라도 20을 초과한다면 모두 20으로 초기화
3. a, b, c 중 c가 최댓값이라면 w(a, b, c-1)+w(a, b-1, c-1)+w(a, b-1,c) 재귀 호출
4. 위의 조건에 해당이 안 된다면
   w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 재귀 호출

문제의 설명대로 위의 코드를 그대로 제출하면 a=15, b=15, c15와 같은 값을 대입하면
a-1이 0이 될 때까지 실행된 노드 수만큼 a-1, a-1, b-1,.. 실행 a-1, b-1을 실행하며 생성된 노드 수만큼
다른 재귀 호출들을 실행하며 많은 중복 연산을 실행하여 시간 내에 값을 도출해 낼 수가 없음

접근 1

딕셔너리를 만들어 (a, b, c)를 key로 value에(a, b, c) 계산된 횟수(0이 되면 return이 1이므로)를 저장하여
(a, b, c) 이하의 계산은 하지 않는 식으로 하려 했으나
구현이 잘되지 않고 횟수를 저장할 마땅한 방법이 떠오르지 않음

답지 확인

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 array[a][b][c]:
        return array[a][b][c]
    if a < b < c:
        array[a][b][c] =  w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return array[a][b][c]
    
    array[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 array[a][b][c]

array = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)]

while True:
    a, b, c = map(int, input().split())
    if a==-1 and b==-1 and c==-1:
        break
    print(f'w({a}, {b}, {c}) = {w(a,b,c)}')

출저:https://velog.io/@noion0511/%EC%8B%A0%EB%82%98%EB%8A%94-%ED%95%A8%EC%88%98-%EC%8B%A4%ED%96%899184

확인하자마자 횟수를 따로 계산할 이유가 없었는데 너무 짧게 생각했단 걸 느꼈고
확인 후에 다시 코드를 작성할 때 3차원 리스트는 생소하여 원래 사용하려 했던 딕셔너리 사용했고
a, b, c의 범위 체크(0~20)를 하기 전에 딕셔너리에 키 확인 후 반환하는 조건문을 사용하여
불필요한 키 생성이 되어 수정하여 제출함
입력받는 부분에서 리스트에 별도로 추가하지 않고 바로 W를 연산하며 출력하여 좀 더 간결하게
코드를 짤 수 있었는데 이번 문제는 집중을 너무 못한 거 같음

내코드

import sys
input = sys.stdin.readline

ilist = list()
while True:
    a,b,c  = map(int,input().split())
    if a == -1 and b == -1 and c == -1:
        break
    ilist.append([a,b,c])
savdict = dict()
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,c) in savdict.keys(): # 0미만,20초과의 값은 위의 조건문에서 초기화 하여 불필요한 key의 생성을 막음
        return savdict[(a,b,c)] 
        
    if a < b and b <c:
        savdict[(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)
    savdict[(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  savdict[(a,b,c)]

for a,b,c in ilist:
    print("w({0}, {1}, {2}) = {3}".format(a,b,c,W(a,b,c)))
    

결과

내 코드 (딕셔너리 사용)

답지(리스트 사용)

여러 답지를 봤을 때 보통 3차원 리스트를 사용하여 문제를 해결하셨는데
딕셔너리 사용 결과가 시간은 빠른데 메모리를 좀 더 사용했음
해당 문제를 해결할 때 리스트와 딕셔너리의 차이점을 좀 더 알 필요가 있을 거 같음