백준 9184. 신나는 함수 실행

https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

 

Dynamic Programming에서는 재귀를 전혀 사용하지 않는 줄 알아서 헤매었으나

동적 프로그래밍의 정의를 검색해본 후로 이해가 갔다 ㅋㅋㅋㅋ

 

단순히 말하면 이전에 구한 답을 재활용하면 된다.

 

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]
	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==b==c==-1:
		break
	print("w({}, {}, {}) = {}".format(a, b, c, w(a,b,c)))

3차원 배열을 활용해서 각 a,b,c,에 대한 답을 저장해놓는다. 이 때 숫자들은 모두 20 이하이므로 21개의 칸을 만들어 배열을 초기화한다.

그리고 만약 dp[a][b][c]에 값이 없다면 구하고, 있으면 반환해주면 된다.