문제

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 w(a, b, c)가 있다.

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)

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)

a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

입력

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

제한
-50 ≤ a, b, c ≤ 50

예제 입력 1

1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1

예제 출력 1

w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1

코드

dp = [[[0] * 21 for _ in range(21)] for _ in range(21)]
def sol(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1

    if a > 20 or b > 20 or c > 20:
        return sol(20, 20, 20)

    if dp[a][b][c]:
        return dp[a][b][c]

    if a < b < c:
        dp[a][b][c]=sol(a, b, c - 1) + sol(a, b - 1, c - 1) - sol(a, b - 1, c)
        return dp[a][b][c]

    dp[a][b][c]=sol(a - 1, b, c) + sol(a - 1, b - 1, c) + sol(a - 1, b, c - 1) - sol(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}) = {sol(a, b, c)}')

dp 문제를 슬슬 풀어보면서 dp의 개념을 쌓아보고자 하였다.

처음엔 문제 그대로 재귀로만 진행하였으나, 시간이 너무 오래걸렸다. 하지만 dp인것을 착안해서 한번 방문한 지점은 저장하여 바로 반환해주는 것이 다이나믹 프로그래밍이라는 것을 깨닫고 그대로 진행하였다.

if dp[a][b][c]:
return dp[a][b][c]
이부분에서 존재했으면 바로 반환해주는 부분이다.

감을 잡기엔 좋은 문제였던거같다!