[알고리즘/파이썬] 백준 9184 신나는 함수 실행

문제링크

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

문제 설명

위 그림과 같이 주어진 재귀함수를 더 효율적으로 출력할 수 있는 프로그램 작성하기

주제

• 동적 계획법

난이도

• 중

풀이 전 생각

재귀함수는 주어졌다. 메모이제이션만 추가하즈아

풀이

import sys

# 메모이제이션 배열
memo = {}

def w(a, b, c, w_memo):

    # 메모에 저장해놓은 값이 있다면 찾아온다.
    if (a, b, c) in w_memo:
        return w_memo[a, b, c]

    if a <= 0 or b <= 0 or c <= 0:
        result = 1
    elif a > 20 or b > 20 or c > 20:
        result = w(20, 20, 20, w_memo)
    elif a < b < c:
        result = w(a, b, c-1, w_memo) + w(a, b-1, c-1, w_memo) - w(a, b-1, c, w_memo)
    else:
        result = w(a-1, b, c, w_memo) + w(a-1, b-1, c, w_memo) 
        + w(a-1, b, c-1, w_memo) - w(a-1, b-1, c-1, w_memo)

    # 메모에 값 저장
    w_memo[(a, b, c)] = result
    print(w_memo)

    return result


while True:
    num1, num2, num3 = map(int, sys.stdin.readline().split())
    ans = w(num1, num2, num3, memo)
    if all([num1 == -1, num2 == -1, num3 == -1]):
        break
    print(f'w({num1}, {num2}, {num3}) = {ans}')

풀이 방법

1. 함수 결과를 저장할 수 있는 'memo' 배열을 생성한다
2. 수식이 끝난 후 'memo'에 값을 저장한다.
3. 만약 이미에 'memo'에 값이 있다면 수식을 진행하지 않고 값만 바로 빼간다.
4. 2,3번을 input값으로 -1,-1,-1이 나올 때까지 반복한다.

문제를 풀고 알게된 개념 및 소감

• 이 문제는 주어진 수식을 정확히 이해하기 보다는 재귀함수와 dp의 전체적인 흐름을 알고 메모이제이션을 사용하는 거에 초점이 맞아있다고 생각한다. 위 그림을 보고 덜컥 겁이나긴 했지만 생각보다 풀이가 간단해서 어제받은 스트레스를 오늘 힐링한거 같다...♡