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

문제

www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

 

 

풀이 및 소스코드

첫 번째와 두 번째 if 문을 통해 dp의 범위를 정할 수 있다.

0보다 작으면 1로 리턴해주고,

20보다 크면 w(20,20,20)으로 통일해주기때문에

dp 는 3차원 모두 다 0~20 까지만 초기화시켜놓으면 된다.

그리고 dp 값이 존재하면 바로 리턴,

없다면 구하고 리턴하면 된다.

쉬웠당 ㅎㅎ ㅎ dp 실버 2인데 쉬웠다니 ..

나 쫌 늘은건가?.. 착각이겠지 ,,, 흑 ㅠ

import sys
input = sys.stdin.readline

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]
    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]

dp = [[[0]*(21) for _ in range(21)] for _ in range(21)]
# 0~20까지므로

while 1:
    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)}')