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

 

dp = [[[0] * 21 for i in range(21)] for i in range(21)] # 값 저장을 위한 3차원 리스트

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] != 0: # 값이 기억하고 있는 것 -> 바로 출력
        return dp[a][b][c]

    if a < b and 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]
    else:  # otherwise
        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:
    num = list(map(int, input().split()))

    if num[0] == -1 and num[1] == -1 and num[2] == -1: # 마지막 입력일 경우 종료
        break
        # %문으로 출력 옵션 편하게 설정
    print("w(%d, %d, %d) = %d" % (num[0], num[1], num[2], w(num[0], num[1], num[2])))

 

코드 설명

dp 값의 저장을 위한 3차원 리스트를 초기화하여 준다. 점화식에 의하여 21을 넘어갈 수는 없으므로 21의 크기로 설정하였다.

반복문을 통해 -1 -1 -1 입력이 나오기 전까지 반복하여 준다.

함수에서는 a, b, c 값을 인자로 받은 다음 주어진 식과 같이 0 이하라면 1을 return, 20 초과라면 w(20, 20, 20) 함수를 return 한다.

만약 dp 리스트에 값이 기억된 것이 있다면 그대로 return 한다. 그리고 주어진 식을 그대로 작성하면서 dp 리스트에 값을 저장하여 준다.

print의 %d 형식을 통하여 조금 더 편하게 출력할 수 있다.

 

Point : 값을 저장하기 위한 dp 리스트를 이용하는 것이 중요하다. 점화식은 주어져 있기 때문에 그대로 작성하면 되고 dp 에 값이 존재할 경우에는 그 값을 reutrn 함으로써 계산의 반복 횟수를 낮출 수 있다.

재귀를 해결하기 위해 dp 리스트를 활용하였지만 값을 모를경우(아직 저장안된경우)에는 점화식처럼 재귀를 이용하여 구성하면 된다.