[백준] 1463. 1로 만들기

❓ 문제 ❓
1로 만들기

💯 문제 풀이 💯
시간 초과를 위해 DP?로 접근했다. dp[i] i 숫자로 가기 위한 최소 횟수를 저장한다. 그러기 위해 dp[i-1] + 1을 저장하고 2 혹은 3으로 나뉠때 dp[i/2 or i/3] + 1중 최솟값을 저장한다.

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