백준 9184
재귀함수가 오래걸리면 다이나믹 프로그래밍을 생각하자.
다이나믹 프로그래밍 -> dp테이블!!
방법1. 다이나믹 프로그래밍
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]
else:
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:
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]
# 입력값이 세개이므로 3차 배열
# 0~20까지이므로 range는 21
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)))
입력값이 a,b,c 세개이므로 3차원 리스트를 사용한다.
if dp[a][b][c]:
return dp[a][b][c]이 부분이 아주 중요하다.!! dp[a][b][c]가 존재하면 바로 리턴해주므로 동일한 값을 계속 연산해야하는 재귀함수와는 비교도 안되게 빨라지기 때문이다.
