백준(BOJ) 1463번 1로 만들기

문제:https://www.acmicpc.net/problem/1463

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

나의풀이 :

동적 계획법을 통해 풀었다.  런타임 에러가 나온다면 MAX에 0이 5개나 7개는 아닌지 봐보자.

코드 ( C ++ )

#include <iostream>

#include <vector>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAX = 10000000;

int cache[MAX + 1];

const int INF = 987654321;

int solve(int x)

{

int& ret = cache[x];

if (ret != -1)

return ret;

if (x == 1) return 0; // 1을 만들었다면 0 반환

ret = INF;

if (x % 3 == 0) ret = min(ret,solve(x / 3) + 1); // 3으로 나뉘었을때는 그 수를 택하므로 +1 해준다

if (x % 2 == 0) ret = min(ret,solve(x / 2)+1);  //2로 나뉘었을때 그 수를 택하므로 +1을 해준다, 

return ret = min(ret, solve(x - 1)+1);  // -1해줄때 그 수를 택하므로 +1 해준다.    나누기 3과 2와 1중 최소를 찾아서 반환해준다.

}

int main()

{

memset(cache, -1, sizeof(cache));

cache[0] = cache[1] = 0;

int num;

cin >> num;

int result = solve(num);

cout << result << endl;

return 0;

}