[백준] 9184번 신나는 함수 실행

문제

접근 방법

• 동적프로그래밍 문제
• w(a, b, c) 결과를 저장하는 리스트 필요
• 문제에 주어진 조건에 맞춰 조건문 생성
• 저장된 리스트에 이미 있는 값이라면 그 값을 반환

나의 풀이

dp =[[[0]*21 for _ in range(21)] for _ in range(21)]

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]

while True:

    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)}')

a, b, c 3개의 문자를 다루고 있으므로 3차원 배열로 생성해주었다.
가장 기본 유형인 것 같다.