https://www.acmicpc.net/problem/9184
여러 가지 생각을 해봤는데 그대로 구현하는.. 코드밖에 생각이 안 나서 다른 사람들의 풀이를 참고했다.
메모이제이션을 이용한다고 한다.
Memoization 메모이제이션: 기억되어야할 것이라는 뜻의 라틴어에서 파생
- 컴퓨터 프로그램이 동일한 계산을 반복적으로 해야 할 때, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하여 전체적인 실행 속도를 빠르게 해주는 기법, 동적 계획법의 핵심 기술
메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)
이번 포스팅에서 다루는 memoization 메모이제이션은 DP 동적 계획법 알고리즘에서 핵심이 되는 기술로 중복 계산을 제거함으로써 프로그램의 전체적인 실행 속도를 빠르게, 성능을 향상할 수 있는
wondytyahng.tistory.com
w함수를 이용하여 a,b,c 인자를 받는다.
문제에 나온 조건을 깔아주고 재귀호출에 따라서 계산한 후 결과를 메모이제이션에 저장하는 코드이다.
# w 함수를 저장할 메모이제이션 배열 초기화
memo = {}
def w(a, b, c):
# 메모이제이션 확인
if (a, b, c) in memo:
return memo[(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 a < b and b < c:
result = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
else:
result = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1)
# 결과를 메모이제이션에 저장
memo[(a, b, c)] = result
return result
# 입력 및 출력 처리
while True:
a, b, c = map(int, input().split())
if a == -1 and b == -1 and c == -1:
break
print(f"w({a}, {b}, {c}) = {w(a, b, c)}")
메모이제이션이라는 새로운 기술을 알게 되어 좋았다!!