✓

태그:

14. 동적 계획법 1

매개 변수가 같으면 항상 같은 값을 반환하는데 이걸 굳이 매번…??

풀이 비스무리한거 보기

주어진 재귀함수의 결과값을 출력하는 문제입니다. 재귀함수는 아래와 같습니다.

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 a<b and b<c:
    return w(a, b, c-1)+w(a, b-1, c-1)-w(a, b-1, c)
else:
    return w(a-1, b, c)+w(a-1, b-1, c)+w(a-1, b, c-1)-w(a-1, b-1, c-1)

이를 그대로 구현하면 최악의 경우 4²⁰번의 함수 호출이 이루어질 수도 있기 때문에 시간 초과는 당연해보입니다. 따라서 memoization 기법을 이용하여 시간을 줄여야 합니다. 특정 (a, b, c)에 대한 w의 리턴값을 저장하고, 나중에 또 쓸 때 재귀함수를 실행할 필요 없이 저장해놓은 값을 리턴하면 시간 상 상당한 개선을 볼 수 있습니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-01-10 12:43:50

---