[백준][파이썬] 9184번 신나는 함수 실행

백준 온라인저지 9184번 신나는 함수 실행

문제풀러 바로가기👇👇👇👇👇👇

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

9184번: 신나는 함수 실행

 

 

문제풀이

---

문제에 점화식이 주어지기 때문에 그것을 그대로 사용하면 된다

다만  if dp[a][b][c]: return dp[a][b][c] 를 통해 재귀함수가 반복되지 않도록만 하자.

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

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 < 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)}")