-
[Python] 백준 - 9184 신나는 함수 실행__Python/__Algorithm 2021. 12. 21. 12:43
# 백준 Silver2
# 9184 신나는 함수 실행
[문제]
링크 : https://www.acmicpc.net/problem/9184
[문제 풀이]
동적계획법
메모이제이션
- 재귀를 사용할 경우, 동일한 계산의 반복으로 시간 효율이 떨어진다.
- 계산한 결과를 메모리에 저장해두어 중복 계산을 방지할 수 있다.
[구현 코드]
import sys MAX = 21 res = [[[0]*MAX for _ in range(MAX)] for _ in range(MAX)] def w(a,b,c): if a <= 0 or b <= 0 or c <= 0: return 1 if a >= MAX or b >= MAX or c >= MAX: return w(20,20,20) # 이미 저장된 값이면 if res[a][b][c]: return res[a][b][c] # 그외 조건 if a < b < c: res[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) else: res[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 res[a][b][c] while True: a,b,c = map(int,sys.stdin.readline().split()) if a == b == c == -1: break print(f'w({a}, {b}, {c}) = {w(a,b,c)}')
피보나치함수(#1003) 문제와 동일하게 풀면 되는데 문제 설명에 당황해 헤맸다.
[실행 결과]
[참고]
- https://jaimemin.tistory.com/619
728x90'__Python > __Algorithm' 카테고리의 다른 글
[Python] 백준 - 2178 미로 탐색 (0) 2022.01.07 [Python] 백준 - 1904 01타일 (0) 2021.12.21 [Python] 백준 - 1003 피보나치 함수 (0) 2021.12.21 [Python] 백준 - 11047 동전 0 (0) 2021.12.20 [Python] 백준 - 1874 스택 수열 (0) 2021.12.20