[백준][21단계 동적 계획법 1] 9184번 /신나는 함수 실행

1. 문제 설명

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

2. 코드

import sys
input = sys.stdin.readline

dp = [[[0] * 21 for _ in range(21)] for _ in range(21)]
vis = [[[False] * 21 for _ in range(21)] for _ in range(21)]

def w(a: int, b: int, c: int) -> int:
    # base
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    # clamp
    if a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)

    if vis[a][b][c]:
        return dp[a][b][c]
    vis[a][b][c] = True

    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)
    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]

out = []
while True:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        break
    out.append(f"w({a}, {b}, {c}) = {w(a, b, c)}")

print("\n".join(out))

3. 풀이 과정

주어진 재귀함수는 한번에 재귀로 4번을 더 해야 하기 때문에 같은 값을 수백번 다시 계산해야 할 수도 있다.

20을 넘어가면 무조건 w(20,20,20)으로 귀결되고 0 이하면 바로 1로 간다.

따라서 0 부터 20까지만 계산하면 된다.

동적 프로그래밍(DP) 테이블을 활용하면 한 번 계산한 값은 다시 계산할 필요가 없다.

따라서 계산한 적이 있는지를 체크하고 없을 때 계산하는 방식으로 변화를 준다.

if 이미 계산한 적 있는지:
    바로 반환
else:
    계산하고 저장

다음 기법을 메모이제이션(Memoization) 또는 Top-Down Dynamic Programming이라 한다.

풀이 설계는 다음과 같이 했다.

w(a,b,c)의 값은 dp[a][b][c]에 하였다.

이미 계산했는지 확인은 vis[a][b][c]에 논리값으로 저장하도록 하였다.

0부터 20까지 범위를 벗어난 경우를 정의하고,

vis 함수에서 True이면 저장된 값을 꺼내고,

False이면 계산한다.

출력값을을 out에 저장해두고,

a,b,c가 -1이 될 때까지 재귀를 진행한다.

4. 자투리 개념

• 동적 프로그래밍(Dynamic Programming)
  - 이미 계산한 값을 버리지 않고 배열에 저장하여 필요한 순간 바로 꺼내 쓰는 방식
  - '작은 문제의 해답을 저장해두고, 그것을 이용해 큰 문제를 해결한다.'