BOJ 9184 - 신나는 함수 실행

문제

백준 온라인 저지 - 9184번

풀이 과정

메모이제이션 으로 재귀 호출을 최적화하는 문제입니다.

문제에서 제시된 함수 구현을 동적 계획법 으로 구현하면 됩니다.

코드

import sys

memo = [[[-1] * 51 for _ in range(51)] for _ in range(51)]


def func(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    if a > 20 or b > 20 or c > 20:
        return func(20, 20, 20)

    if memo[a][b][c] != -1:
        return memo[a][b][c]

    if a < b < c:
        memo[a][b][c] = func(a, b, c - 1) + func(a, b - 1, c - 1) - func(a, b - 1, c)
    else:
        memo[a][b][c] = func(a - 1, b, c) + func(a - 1, b - 1, c) + func(a - 1, b, c - 1) - func(a - 1, b - 1, c - 1)

    return memo[a][b][c]


def solution(a, b, c):
    output = func(a, b, c)

    return f"w({a}, {b}, {c}) = {output}\n"


if __name__ == '__main__':
    while 1:
        a, b, c = list(map(int, sys.stdin.readline().split()))

        if [a, b, c] == [-1, -1, -1]:
            break

        answer = solution(a, b, c)
        sys.stdout.write(answer)