반응형
https://www.acmicpc.net/problem/9184
9184번: 신나는 함수 실행
입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.
www.acmicpc.net
문제에 점화식이 다 나와있어서 점화식을 따로 구할 필요는 없었다. 동적계획법 문제이기 때문에 재귀함수의 결과만 리스트에 저장해두면 됐었다!
dp = [[[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 dp[a][b][c] != 0:
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]
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:
a, b, c = map(int, input().split())
if a == -1 and b == -1 and c == -1:
break
print('w(%d, %d, %d) = %d' % (a, b, c, w(a, b, c)))
반응형
'Algorithm > 백준' 카테고리의 다른 글
| [백준/Python] 01타일 (0) | 2021.10.03 |
|---|---|
| [백준/Python] 골드바흐의 추측 (0) | 2021.10.03 |
| [백준/Python] 베르트랑 공준 (0) | 2021.10.01 |
| [백준/Python] 피보나치 함수 (0) | 2021.09.30 |
| [백준/Python] 스도쿠 (0) | 2021.09.21 |