바텀업으로 풀어보자.

• 일단 탑다운 코드를 작성해보면, 이렇다.

문제 해결 전략

• 1) 탑다운 입장에서 한번에 진행되는 것들 중 3개를 확인하므로 이렇게 작성함.

// go(x) = max( go(x - 1) , go( x / 3) , go( x / 2 ) );

• 2) 문제를 보면, memo[2] = 1, memo[3] = 1, 이고
  1의 입장에서 1이 되는 연산수는 0개이므고, memo[1] = 0이다.

• 3) 그리고 나의 입장에서 전단계를 선택하면서 반드시 카운팅 +1을 해야한다.

정답코드

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

using namespace std;



int memo[1000001];


int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int x;
	cin >> x;

	// go(x) = max( go(x - 1) , go( x / 3) , go( x / 2 ) );


	//memset(memo, 987654321, sizeof(memo));
	fill(memo, memo + 1000001, 987654321);

	memo[1] = 0;
	memo[2] = 1;
	memo[3] = 1;
	for (int i = 2; i <= x; ++i)
	{
		memo[i] = min(memo[i - 1] + 1, memo[i]);

		if (i % 2 == 0)
			memo[i] = min(memo[i], memo[i / 2] + 1);

		if(i % 3 == 0)
			memo[i] = min(memo[i], memo[i / 3] + 1);

	}

	cout << memo[x];


	return 0;

}