go(x)가 "x에서 1로 가는 비용"임을 생각하면 재귀를 돌리는 과정 전체를 떠올릴 필요는 없습니다.

예를 들어, x가 6이라면 다음 세 가지를 고려할 것입니다.

1. 1을 뺀다. 1을 빼는 데 비용 1이 들고, 그 상태에서 1에 도착하는데 비용 go(5)가 들기 때문에 비용은 go(5)+1
2. 2로 나눈다. 비용은 go(3)+1
3. 3으로 나눈다. 비용은 go(2)+1

여기서 go를 다시 시뮬레이션하지 말고, 미리 알고 있다고 가정한 뒤 값을 대입하면 편합니다.

dp는 문제 정의를 명확히 하면 이해하기 쉬운 경우가 많습니다.

이 문제의 경우 go라는 함수가 결과적으로 반환하는 값이 무엇인지 생각해봅시다.

go(x) = "x를 1로 만들기 위한 최소 연산 횟수" 으로 정의할 수 있죠. 이 경우 문제의 정답은 go(n)이 됩니다. 그리고 문제 정의에 따라 일단 go(1) = 0이 되겠죠(1을 1로 만들기 위한 최소 연산 횟수는 0이므로).

그러면 이 때 나머지 x값들에 대해서 go(x)를 어떻게 계산할 수 있을까요? 문제 설명을 보면 저희가 사용할 수 있는 연산은 1을 빼거나, 2로 나누거나, 3으로 나누거나 셋 중 하나입니다. 그러면 세 가지 연산 중에서 가장 연산 횟수가 적은 경우가 답이 될 거라고 생각할 수 있습니다. x=6인 경우를 예로 들면,

1을 빼는 연산을 수행한 경우 5(6-1)를 1로 만들기 위한 최소 연산 횟수에 1을 더한 값(= go(5) + 1),

2로 나누는 연산을 수행한 경우 3(6/2)을 1로 만들기 위한 최소 연산 횟수에 1을 더한 값(=go(3) +1),

3으로 나누는 연산을 수행한 경우 2(6/3)를 1로 만들기 위한 최소 연산 횟수에 1을 더한 값(=go(2)+1)

중에서 가장 작은 값이 6을 1로 만들기 위한 최소 연산 횟수가 될 겁니다. 세 연산 중에 하나만 수행할 수 있고, 각 연산을 수행한 다음 단계에서 최소 연산 횟수를 모두 고려했으니까요. 그러면 go(x)는 아래와 같이 정의 할 수 있습니다.

go(x) = min(go(x-1), go(x/2), go(x/3)) + 1 (물론 go(x/2), go(x/3)은 각각 x가 2의 배수 혹은 3의 배수일 때만 고려하겠죠)

하지만 이대로 그냥 구현하면 함수 호출 횟수가 지수적으로 증가하기 때문에 시간 초과가 납니다. 여기서, go 함수의 경우 인자 x가 동일하면 리턴값도 반드시 동일합니다. 이 것도 문제 정의를 생각해보면 쉽게 이해할 수 있는데, "x를 1로 만들기 위한 최소 연산 횟수"는 x가 동일하면 항상 일정한 값일테니까요.

그래서 여기서 생각할 수 있는 최적화가 바로 "한 번 계산한 값은 다시 계산하지 말자"라는 것입니다. 어떤 x 값에 대해 go(x)를 이전에 계산한 적이 있다면 다시 또 계산하지말고 이전에 계산했던 값을 저장해뒀다가 그걸 바로 다시 돌려주자는 거죠. 이게 dp의 핵심인 메모이제이션(memoization)입니다. 그래서 보통 dp 문제의 경우 문제에서 제시하는 조건을 만족하도록 모든 경우를 탐색하는 함수를 작성한 다음, 이전에 계산한 적 있는 값인 경우 저장해뒀다가 다시 계산하지 않고 돌려주는 로직만 추가해주면 되는 경우가 많습니다.

감사합니다  jh05013님   jwvg0425님 두분글을 읽어보니 제가

if(dp[n]>0) return dp[n];     <-------

이부분을 유심히 생각 안했었던것같아요 감사합니다