[백준]Baekjoon1463(Dynamic Programming)

풀이

첫번째 풀이는 bottom-up 방식을 사용하였다.

연산을 사용해서 끝나는 마지막 값이 1이므로 초기값은 m[1] = 0으로 주었다.

그 후 반복문을 사용하여 구하고자 하는 수까지 반복하면서 

세가지 방법중에 가장 작은값이 나오는것을 배열값으로 주었다.

아래는 그 점화식과 코드이다.

f(n) = min(f(n-1) + 1, f(n/3) + 1, f(n/2) + 1))

#include <iostream>
#include <vector>
#include <cstring>

#define SIZE 1000000 //입력값으로 줄 수 있는 최댓값
using namespace std;

int memo[SIZE + 1]; //값을 저장하는 배열

int main()
{
	memset(memo, -1, sizeof(int)*(SIZE + 1)); //배열의 모든 값들을 -1로 초기화
	memo[1] = 0; // 초기값
	int num; cin >> num;
	for (int i = 2;i <= num; i++) {
		memo[i] = memo[i - 1] + 1; 
		if (i % 2 == 0) memo[i] = (memo[i / 2] + 1 < memo[i]) ? memo[i / 2] + 1 : memo[i]; 
		if (i % 3 == 0) memo[i] = (memo[i / 3] + 1 < memo[i]) ? memo[i / 3] + 1 : memo[i];
	}
	cout << memo[num];
}

다음의 풀이는 top - down 방식이다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

#define SIZE 1000001 
using namespace std;

int memo[SIZE]; 

int f(int x) {
	if (x < 2) return 0;
	else if (x == 2 || x == 3) return 1;
	else if (memo[x] > -1) return memo[x];
	memo[x] = f(x - 1) + 1;
	if (x % 3 == 0) memo[x] = min(memo[x], f(x / 3) + 1);
	else if (x % 2 == 0) memo[x] = min(memo[x], f(x / 2) + 1);
	return memo[x];
}
int main()
{
	memset(memo, -1, sizeof(int)*(SIZE));
	int num; cin >> num;
	printf("%d\n", f(num));
}