[C++]BOJ 1463 - 1로 만들기

크게 두 가지 경우의 수가 있다.

1. 3로 나누어 떨어질 경우
2. 3으로 나누어 떨어질 경우

3번 조건은 언제나 적용할 수 있기 때문에 처음부터 계산하고 시작한다.
2와 3의 공배수 같은 경우는 2와 3 둘 다 나누어 떨어지기 때문에 다른 조건을 만들어야 하나 싶었지만 어차피 dp[]에 저장된 값을 같은 i를 돌고 있을 때 다시 확인하므로 상관이 없다.

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