[백준] 1로 만들기 1463번 (c++)

출처 : 1463번: 1로 만들기 (acmicpc.net) 

1463번: 1로 만들기

해결 방법

dp문제 이다. top-down으로 해결 하였다.

3으로 나누어 지면 f(n/3)을 호출해서 저장하고

2로 나누어 지면 f(n/2)을 호출해서 저장하고

f(n-1)을 호출해서 저장해 가장 작은 값에다가 +1을 더해 주어서 리턴하였다.

#include <iostream>
#include <memory.h>
#include <algorithm>

using namespace std;
int dp[100001];
const int INF = 987654321;

int f(int n) {
	if (n == 1) return 0;
	int& ret = dp[n];
	int tree = INF, two =INF, one = INF;
	if (n % 3 == 0) {
		tree = f(n / 3);
	}
	if (n % 2 == 0) {
		two = f(n / 2);
	}
	one = f(n - 1);
	ret = min(tree,min(two, one)) + 1;
}

int main() {
	memset(dp, -1, sizeof(dp));
	int n;
	cin >> n;
	cout << f(n);
	return 0;
}