[v.동적 계획법 1-신나는 함수 실행-9184]BAEKJOON_Python

220127 작성

<본 블로그는 BAEKJOON 을 참고해서 저만의 풀이를 작성하였습니다>

 

 

 

9184

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력

다음과 같은 재귀함수 w(a, b, c)가 있다.

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)

 

 

 

 

 

내 풀이

import sys
input = sys.stdin.readline

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)

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



dp = [[[0 for _ in range(21)] for _ in range (21)] for _ in range (21)]
while True:
    a,b,c = map(int, input().split())
    if a==-1 and b==-1 and c==-1:
        break
    print("w({}, {}, {}) = {}".format(a,b,c,w(a,b,c)))

 

 

 

 

 

 

2 2 2
w(2, 2, 2) = 4
10 4 6
w(10, 4, 6) = 523

 

 

 

 

 

참고했숩니당,,

왜 내꺼는 타임에러 뜨징..?

https://seraup.dev/8

백준 9184번 신나는 함수 실행 (Python)