원래 dp가 매우 어렵습니다. 그나마 이 문제는 dp 문제 중에서는 중하위 정도 수준이라고 보여지는데, 아이디어도 떠올리기 어렵고 코드를 분석하기도 참 힘든 분야 중 하나입니다.

답변 감사합니다 ㅠ

@rlagh33

재귀를 이용해서 푸셨나요?? 재귀까지 갈 필요없는 문제같은데..

dp문제의 핵심은 각 step당 최적값을 기록하고, 기록된 값을 이용해서 다음step의 최적값을 찾는것 입니다.

예제인 10의 경우에는 아래와 같은 아이디어로 접근하실 수 있어요.

10의 경우 다음step으로 갈 수 있는 경우는 9 혹은 5로 갈 수 있습니다. (-1,/2)

DP테이블 : 10 9 8 7 6 5 4 3 2 1 

                    0  1 0 0 0 1 0 0 0 0

9의 경우엔 9/3인 3과 9-1인 8로 갈 수 있겠네요.

DP테이블 : 10 9 8 7 6 5 4 3 2 1 

                    0  1 2 0 0 1 0 2 0 0

8의 경우엔 8/2인 4와 8-1인 7로 갈 수 있구요.

DP테이블 : 10 9 8 7 6 5 4 3 2 1 

                    0  1 2 3 0 1 3 2 0 0

7의 경우엔 6밖에 갈 수 없습니다.

DP테이블 : 10 9 8 7 6 5 4 3 2 1 

                    0  1 2 3 4 1 3 2 0 0

이제 5의 경우를 살펴봐야 하는데, 5에는 1번만에 갈 수 있다는 결론이 나와있습니다.

그럼 5에서 이동할 수 있는 경우의 수는 4밖에 없는데, 4는 이미 3번을 이용하여 경유한 기록이 있네요.

이걸 더 적은값인 2로 갱신시켜 줍니다.

DP테이블 : 10 9 8 7 6 5 4 3 2 1 

                    0  1 2 3 4 1 2 2 0 0

이제 4의경우입니다.

4는 4/2인 2로 갈 수도 있고, 4-1인 3으로 갈 수도 있습니다.

DP[3] 은 2, DP[2]는 0 인데, DP[3]의 경우는 2+1인 3으로 갱신할 시 , 기존 값보다 더 크게 됩니다. 따라서 PASS하고

2의 경우는 방문한 기록이 없으므로, DP[4]+1인 3으로 갱신시킵니다.

DP테이블 : 10 9 8 7 6 5 4 3 2 1 

                    0  1 2 3 4 1 2 2 3 0

마지막으로 3의 경우를 위와 같은 원리로 살펴보고 나면, 모든 경우를 최적화 된 방법으로 갈 수 있는 TABLE이 만들어지고

우리는 1로 갈 경우를 찾아보는 것 이기 때문에 DP[1]의 값을 출력해주시면 됩니다.

위 방법은 DP[STEP]에 기록 된 경우가 "최적의 해"라는 확신을 할 수 있기때문에, 이를 이용한 풀이방법입니다.