백준 1463(DP) 1로 만들기

DP는 거의 처음 풀어보는 문제다.
다른 문제를 먼저 풀다가 도저히 이해가 안돼서 바킹독 실전 알고리즘 유튜브를 보고 정리해보려고 한다.

백준: https://www.acmicpc.net/problem/1463

1. 테이블 정의
   D[i]=i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값

2. 점화식 찾기

   D[12]=?

   1) 3으로 나누거나(D[12]=D[4]+1)
   2) 2로 나누거나(D[12]=D[6]+1)
   3) 1을 빼거나(D[12]=D[11]+1)
   즉, D[12]=min(D[4]+1,D[6]+1,D[11]+1)

   D[k]=?

   1) 3으로 나누어지면 3으로 나누거나(D[K]=D[K/3]+1)
   2) 2로 나누어지면 2로 나누거나(D[K]=D[K/2]+1)
   3) 1을 빼거나(D[K]=D[K-1]+1)

3. 초기값 정의하기
   D[1]=0