[BOJ] 1463 1로 만들기 - 메모이제이션

매우 간단한 문제이다.

나눗셈을 하는것이 무조건 이득이다.

75를 예로 들어보자

75 는 2^3 * 3 ^ 2 + 3 이다.

결국 몇으로 나눌지가 문제이다

이것을 재귀적으로 분기 할 수 있도록 식을 구성한다.

반복되는것이 있을 수 있으므로 메모리에 저장해둔다.

 

#include <algorithm>
#include <stdio.h>
#include <iostream>
 
int Memoization[1000001] = { 0 , };
 
 
int RecCalc(int Number)
{
	if (Number < 2) return 0;
 
	int Select2 = 0;
	int Select3 = 0;
 
	if (0 != Memoization[Number])
		return Memoization[Number];
 
	if (0 != Memoization[Number / 3])
		Select3 = Memoization[Number / 3] + 1 + Number % 3;
 
	else
		Select3 = RecCalc(Number / 3) + 1 + Number % 3;
 
	if (0 != Memoization[Number / 2])
		Select2 = Memoization[Number / 2] + 1 + Number % 2;
 
	else
		Select2 = RecCalc(Number / 2) + 1 + Number % 2;
 
	Memoization[Number] = std::min(Select2, Select3);
	return Memoization[Number];
}
 
int main()
{
	int N;
	std::cin >> N;
	std::cout << RecCalc(N);
 
	return 0;
 
}