BAEKJOON #9184 신나는 함수 실행

이 문제의 저작권은 BAEKJOON에 있습니다.

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

 

풀이

1. dp리스트를 미리 생성한다. 값은 0으로 하고 문제에서 20이상의 값은 모두 20으로 재귀하기 때문에 21크기 리스트를 만든다.
2. 문제의 식을 그대로 쓴다.
3. 재귀하기 전 이미 dp리스트에 값이 있으면 그대로 return하는 코드를 추가한다.

# 신나는 함수 실행
# https://www.acmicpc.net/problem/9184

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

    # 아래 조건을 실행하기 전에    
    # dp리스트에 이미 존재하면 그대로 리턴한다.
    if dp[a][b][c]:
        return dp[a][b][c]
    # dp리스트에 없으면 조건을 실행
    if a<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]

# 20보다 크면 20으로 재귀하기 때문에 리스트 크기를 20까지 설정 
dp = [[[0 for _ in range(21)] for _ in range (21)] for _ in range (21)]
while True:
    a,b,c = map(int, input().split())
    # 종료 조건 -1 -1 -1 
    if a==-1 and b==-1 and c==-1:
        break
    print("w({}, {}, {}) = {}".format(a,b,c,w(a,b,c)))