1463번 1로 만들기(DP) - ☆

#문제링크 : https://www.acmicpc.net/problem/1463

<전략>

1. 수 N에서 한번 연산하고 다음수로 넘어간 수를 (1, N)수라 하면, M번 연산하고 넘어간 수는 (M, N)이다.

2. (M-1, N)의 연산횟수의 최소값은 (M, N)의 최소값 + 1 이다. M-1 -> M 연산 한번을 더 했기 때문.

3. N의 최소 연산 횟수를 num[N]에 저장하고, 이후에 N보다 큰 값이 나올때, 저장된 값을 사용한다.

Code