9184번

딱 떠오르는 건 재귀함수 정도입니다. 그러나 많은 시간을 요구하니 다른 방법으로 풀어보라고 합니다. 우선 눈에 보이는 특징은 모든 parameter의 변위가 1이 최대라는 점입니다. 그리고 입력 값이 20보다 크면 20으로 줄여주는 친절함도 눈에 보입니다.

그나저나 왜 w(15, 15, 15)를 매우 오랜 시간이 걸리는 예로 들어준 걸까요? 적어보면 다음과 같은 과정이 포함됩니다.

w(15, 15, 15) = w(14, 15, 15) + w(14, 14, 15) + w(14, 15, 14) - w(14, 14, 14)

세 값이 하나라도 다르다면 둘 중 먼저 종결조건에 도달하는 경우가 생기지만 모두 같은 값이라면 셋이 동시에 종결조건에 이르러야 하기 때문에 긴 시간이 걸린다는 뜻이었습니다. 그런데 w(14, 14, 14)는 w(15, 15, 15)를 계산함에 필연적으로 등장하고 w(13, 13, 13)이 w(14, 14, 14)를 계산할 때 필연적으로 등장할 것이라는 사실을 짐작할 수 있습니다. 그렇다면, 재귀를 풀어가는 도중에 종결조건을 확인하고 다음 계산을 실행하기 전에 a, b, c의 값을 오면서 계산을 했다면 많은 재귀를 없앨 수 있을 것입니다.

삼차원 배열을 만들어 a, b, c의 값을 저장하기로 합니다. 어떤 배열 arr[a][b][c]의 값이 0이라면 단 한 번도 a, b, c의 값을 계산 한 적이 없다는 뜻이며 0이 아니라면 계산을 했다는 뜻이기 때문에 그대로 사용하면 됩니다.

정말로 if ( arr[_a][_b][_c] != 0) return arr[_a][_b][_c]; 한 문장으로 많은 시간을 단축했습니다.