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

며칠째 규칙을 못 찾겠어서 검색을 해버렸다.. 그런데 매우 간단하더라. 동적이니까 그냥 저장을 미리 해버리는 방식이다. 최대한 재귀호출을 줄이는 것이다.

코드

import sys
input = sys.stdin.readline

lst = [[[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 lst[a][b][c]:
        return lst[a][b][c]
    if a<b and b<c:
        lst[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return lst[a][b][c]
    lst[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 lst[a][b][c]

while True:
    a, b, c = map(int, input().split())
    if a==-1 and b==-1 and c==-1:
        break
    # print('w(', a, ', ', b, ', ', c, ') = ', w(a, b, c), sep='')
    print(f'w({a}, {b}, {c}) = {w(a, b, c)}')

• w(a, b, c) 값을 저장할 21x21x21 3차원 배열을 만든다. (인덱스는 0부터이지만 주어진 문제의 a, b, c는 1부터 시작하기에 21 크기를 만든 것이다.)
• lst[a][b][c]에 해당값이 저장되어 있으면 재귀를 거치지 않고 바로 반환하도록 한다.
  여기서 if lst[a][b][c]: 의 위치가 중요한데, 20보다 큰 수가 들어오면 lst에 접근이 불가능하다. 따라서 if a>20 or b>20 or c>20: 이후에 저장해야 한다.
• 또한 파이썬의 f-string을 사용해서 마지막에 저렇게 출력도 가능하다!!

결과