[Baekjoon]백준 9184 신나는 함수 실행(실버 2) - Python

문제설명 1

문제설명 2

문제를 살펴보면 재귀적으로 호출하여 답을 구하는 코드가 존재한다

이를 동적 계획법으로 바꾸어 빠른 출력을 위한 코드를 작성하는 것이 문제이다

일단 재귀호출을 하는 코드를 그대로 작성해보면 

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:
        return w(20, 20, 20)
    elif a < b < c:
        return w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
    else:
        return w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
    
while True:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        break
    result = w(a, b, c)
    print(f'w({a}, {b}, {c}) = {result}')

이렇게 되고, 이 코드로 예제에 있는 50 50 50을 넣어보면 바로 답이 안 나오고 계산하는 시간이 오래 걸린다

리스트를 사용하는 방법도 있지만, 튜플 사용하는 연습도 해볼 겸 튜플로 코드를 작성하였다

기존의 코드와 동일하게 동작을 하되, 튜플에 이미 존재하는 값이 들어온다면 다시 return하여

불필요한 계산으로 인한 시간사용을 줄였다

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
    elif a > 20 or b > 20 or c > 20:
        memo[(a, b, c)] = w(20, 20, 20, memo)
    elif a < 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)
        )
    else:
        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:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        break
    result = w(a, b, c)
    print(f'w({a}, {b}, {c}) = {result}')

memo 딕셔너리를 활용하여 동일한 입력에 대해 재계산하지 않도록 하였다