https://www.acmicpc.net/problem/9184
- 다이나믹 프로그래밍
- 재귀
import sys
input = sys.stdin.readline
dp = [[[None]*21 for _ in range(21)] for _ in range(21)]
# dp[0][0][0] = 1로 초기화
dp[0][0][0] = 1
def solve(a, b, c):
if a <= 0 or b <= 0 or c <= 0:
return dp[0][0][0]
if a > 20 or b > 20 or c > 20:
return solve(20, 20, 20)
if dp[a][b][c] is not None:
return dp[a][b][c]
if a < b and b < c:
dp[a][b][c] = solve(a, b, c-1) + solve(a, b-1, c-1) - solve(a, b-1, c)
return dp[a][b][c]
dp[a][b][c] = solve(a-1, b, c) + solve(a-1, b-1, c) + \
solve(a-1, b, c-1) - solve(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
ans = solve(a, b, c)
print(f"w({a}, {b}, {c}) = {ans}")
if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
1
if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
w(20, 20, 20)
if a < b and b < c, then w(a, b, c) returns:
w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
otherwise it returns:
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
위와 같은 재귀함수 w(a, b, c)가 있을 때, 다이나믹 프로그래밍을 이용하여 결과값을 더 빨리 구할 수 있게 프로그래밍한다.
dp
를 만든다.w(a, b, c)
의 값은 dp[a][b][c]
에 저장된다.a <= 0 or b <= 0 or c <= 0
이면 바로 1로 초기화 해둔 dp[0][0][0]
을 리턴한다.a > 20 or b > 20 or c > 20
이면 solve(20, 20, 20)
을 호출, 결과적으로 dp[20][20][20]
의 값을 리턴한다.
위 두 조건에서 걸리지 않은 경우는 a, b, c가 모드 0~20 사이의 값이므로 dp[a][b][c]
가 존재하면 바로 그 값을 리턴한다.
a < b and b < c
인 경우와 그 외(else
)의 경우에는 문제에서 주어진 w(a, b, c)
함수의 동작을 지금까지의 방식과 유사하게 solve를 이용해서 코드를 작성해주면 된다.