🥚문제링크

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

• 다이나믹 프로그래밍
• 재귀

---

🍳코드

import sys
input = sys.stdin.readline


dp = [[[None]*21 for _ in range(21)] for _ in range(21)]
# dp[0][0][0] = 1로 초기화
dp[0][0][0] = 1


def solve(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return dp[0][0][0]

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

    if dp[a][b][c] is not None:
        return dp[a][b][c]

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

    dp[a][b][c] = solve(a-1, b, c) + solve(a-1, b-1, c) + \
        solve(a-1, b, c-1) - solve(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

    ans = solve(a, b, c)

    print(f"w({a}, {b}, {c}) = {ans}")

---

🧂아이디어

DP

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)

위와 같은 재귀함수 w(a, b, c)가 있을 때, 다이나믹 프로그래밍을 이용하여 결과값을 더 빨리 구할 수 있게 프로그래밍한다.

• 각각 0에서 20까지의 인덱스를 갖는 3차원 리스트 dp를 만든다.
  • 0에서 20까지만 만들면 되는 이유는 위 함수가 0보다 작거나 같으면 무조건 1을 리턴하고, 20을 초과하면 무조건 w(20, 20, 20)을 리턴하기 때문

• w(a, b, c)의 값은 dp[a][b][c]에 저장된다.

• a <= 0 or b <= 0 or c <= 0이면 바로 1로 초기화 해둔 dp[0][0][0]을 리턴한다.

• a > 20 or b > 20 or c > 20이면 solve(20, 20, 20)을 호출, 결과적으로 dp[20][20][20]의 값을 리턴한다.

• 위 두 조건에서 걸리지 않은 경우는 a, b, c가 모드 0~20 사이의 값이므로 dp[a][b][c]가 존재하면 바로 그 값을 리턴한다.

• a < b and b < c인 경우와 그 외(else)의 경우에는 문제에서 주어진 w(a, b, c)함수의 동작을 지금까지의 방식과 유사하게 solve를 이용해서 코드를 작성해주면 된다.