[백준 1463] 1로 만들기

요구사항

주어진 수를 1로 만들기 위한 최소 연산 횟수

 

풀이

전형적인 dp문제이다

d[i]의 최소값은 -1. /2, /3 셋 중에서 최소에다가 +1한 값이랑 동일하다

 

탑다운, 다운업 방식으로 풀 수있다

다운 업 방식이 6배 정도 빠르다

 

탑다운 방식은 너무 많이 func가 호출되기 때문인듯하다

함수를 call하는 비용은 단순 함수의 반복 보다 큰 것으로 알고있다

 

#pragma warning(disable:4996)
#include <vector>
#include <queue>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <functional>
#include <algorithm>

using namespace std;

int n, m, t, s, g, h;
int dp[1000100];
int func(int now) {
	//cout << now << endl;
	if (now == 0)
		return 0;
	if (now == 1)
		return 0;
	if (now == 2)
		return 1;
	if (now == 3)
		return 1;
	int &ret = dp[now];
	if (ret != -1) return dp[now];
	int temp = 987654321;
	int a, b, c;
	if (now % 2 == 0) {
	//	cout << "B" << endl;
		temp = min(temp,func(now / 2));
	}
	if (now % 3 == 0) { 
	//	cout << "C" << endl;
		temp = min(temp,func(now / 3));
	}
	temp = min(func(now - 1), temp);
	ret = 1 + temp;
	//cout << a << " " << b << " " << " " << c << endl;
	return dp[now]=ret;

}
int main() {
	scanf("%d", &n);
	memset(dp, -1, sizeof(dp));
	/*
	for (int i = 2; i <= n; i++) {
		dp[i] = 1 + dp[i - 1];
		if (i % 2 == 0) dp[i] = min(dp[i], 1 + dp[i / 2]);
		if (i % 3 == 0) dp[i] = min(dp[i], 1 + dp[i / 3]);
	}
	cout << dp[n] << endl;
	*/
	cout << func(n) << endl;
}