1로 만들기

문제

정수 N에 다음 세 가지 연산을 쓸 수 있다.

1. N이 3으로 나누어 떨어지면 3으로 나눈다.
2. N이 2로 나누어 떨어지면 2로 나눈다.
3. 1을 뺀다.

이 연산을 적절히 골라 N을 1로 만드는 데 필요한 최소 횟수를 구하라.

예: 10 → 9 → 3 → 1 (3번)

점화식: dp[i] = min(dp[i-1], dp[i/2], dp[i/3]) + 1 (나누기는 나누어 떨어질 때만)