백준[ 9148 | Python ] 신나는 함수 실행

문제

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

풀이

각 변수가 들어갈 수 있는 dp테이블을 먼저 선언한다.
a,b,c가 들어갔을 때의 w return 값을 dp테이블에 저장하여
값이 존재할 때 참조하여 풀이 하게끔 한다.
dp테이블은 미리 선언해서 그 전의 입력에 대한 결과들을 저장하여 사용할 수 있도록 한다.

import sys
input = sys.stdin.readline
dp = [[[0]*(50) for _ in range(50)] for _ in range(50)]

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 dp[a][b][c]:
        return dp[a][b][c]

    if a < b and b < c:
        dp[a][b][c] = w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)
        return dp[a][b][c]
    else:
        dp[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 dp[a][b][c]
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)}")
            

생각 & 정리

메모이제이션의 정석 같은 문제였다.
값이 없을 때는 직접 함수가 실행되면서 그 과정에 생성된 값들을 dp테이블에 넣어주고
그 다음부터 함수 실행 도중에 dp테이블에 값이 존재한다면 직접 함수를 수행하지 않고
테이블 내의 값을 바로 참조 하여 연산의 수행을 크게 줄여주는 점이 흥미로웠다.
아직 DP에 대해서 감을 잡기가 힘들다. 다른 유형들 보다 더 많은 문제들을 접해봐야 할 것 같다.