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

입력받은 수를 3으로 나누거나 2로 나누거나 1을 빼가면서 1로 만드는데 최소 횟수를 구하는 문제이다.

나는 재귀 함수로 작성했는데 아마 2중 for문으로도 해결할수 있지 않을까 생각하지만 잘 모르겠다.

답은 항상 n을 3으로 나누고 시작할때, n을 2로 나누고 시작할때, n-1로 시작할때 이 세가지 경우중 하나이다

점화식 도출은 이렇게 했다.

n을 3으로 나누고 시작할때 횟수(3으로 나눌수 없다면 초기값)와 2로 나누고 시작할때의 횟수 중  적은 값을 선택하고 그 값과 n에서 1을빼고 시작할때의 횟수를 비교한다.

#=> $ f(n) = min( f(n-1), min( f(n/3), f(n/2) ) ) $

단, f(n) = n을 1로 만드는 최소 비용을 나타내는 함수이므로 항상 최소 값을 비교하기 위해서 초기값을 매우 큰 수로 설정하며, n이 1~3일때 최소 횟수를 이미 알고 있으므로 미리 값을 집어넣어줬다.

#include<iostream>
#include<string>
#define INT_MAX 987654321

using namespace std;

int* r = new int[1000001];

int min(int x,int y){return x<y?x:y;}

int solve(int x){
 	if(r[x] != INT_MAX) return r[x];
 	int& ret = r[x];
 	if(x%3==0) ret = solve(x/3);
 	if(x%2==0) ret = min(ret, solve(x/2));
 	ret = min(ret, solve(x-1))+1;
 	return ret;
}
int main(){
	int n,i;
	cin>>n;
	for(i=0;i<=n;i++)
        r[i] = INT_MAX;
	r[1] = 0;
	r[2] = 1;
	r[3] = 1;
	cout << solve(n);
}