백준 알고리즘
9184번 신나는 함수 실행
위에 제시된 함수는 재귀함수의 형태이다.
코드를 작성하는 것에 큰 어려움은 없다.
단순히 문제에서 제시해 준 코드를 그대로 문법에 맞게 옮기면 된다.
그러나 어떤 장치도 없는 단순한 재귀함수로 위의 함수를 구현하면 시간초과가 뜨게 된다.
시간 제한은 1초이다.
이 재귀함수가 보다 효율적으로 작동하기 위해서는 동적 계획법을
이용해야 한다.
다이나믹 프로그래밍의 Memoization 기법을 이용하여 동일한 계산을 여러 번 반복하지 않도록 한다.
소스 코드를 통해 이를 어떻게 구현했는지 살펴본다.
형광펜으로 칠해진 곳이 핵심이다.
dp 리스트에 이미 계산된 결과들을 저장하여 재귀의 깊이가 더 깊어지지 않도록 했다.
처음에 dp 리스트를 전부 0으로 초기화했기 때문에
dp[a][b][c] !=0, 즉, 이미 계산한 적이 있는 경우에 바로 그 값을 반환하도록 한다.
이 부분을 제외하면 문제에서 제시한 코드와 동일하다.
Whiplash We Flash