[이것이 코딩 테스트다] 1로 만들기

❓ 문제 ❓
x가 주어질때 1로 만들 수 있는 최소의 연산 횟수를 구하여라

💯 풀이 방법 💯
점화식 min(직전, /2. /3, /5) + 1

#include <iostream>
#include <algorithm>
using namespace std;
int dp[30001];
int main() {
	int num; cin >> num;
	for (int i = 2; i <= num; i++) {
		dp[i] = dp[i - 1] + 1;
		if (i % 5 == 0)
			dp[i] = min(dp[i], dp[i / 5] + 1);
		if (i % 2 == 0)
			dp[i] = min(dp[i], dp[i / 2] + 1);
		if (i % 3 == 0)
			dp[i] = min(dp[i], dp[i / 3] + 1);
	}
	cout << dp[num];
}