백준 9184번 "신나는 함수 실행"
문제
풀이
문제에 유사코드가 적혀있어 어려운 문제는 아니였다.
다만 유사코드 그대로 코드를 구현하면 무조건 시간초과가 뜨게되니 메모이제이션을 이용하자.
메모이제이션
- 동일한 계산을 반복해야 할 경우 한번 계산한 결과를 메모리에 저장해 두었다가 꺼내쓰는 방법
- DP의 핵심!
Python 코드
import sys
input = sys.stdin.readline
arr = [[[0]*21 for i in range(21)] for j in range(21)]
def w(a, b, c):
if a<=0 or b<=0 or c<=0:
return 1
elif a>20 or b>20 or c>20:
return w(20,20,20)
elif arr[a][b][c]:
return arr[a][b][c]
elif a<b<c:
arr[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
return arr[a][b][c]
else:
arr[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 arr[a][b][c]
while 1:
a,b,c=map(int, input().split())
if (a,b,c)==(-1,-1,-1):
break
print(f'w({a}, {b}, {c}) = {w(a, b, c)}')
Author And Source
이 문제에 관하여(백준 9184번 "신나는 함수 실행"), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kgpaper/백준-9184번-신나는-함수-실행저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)