문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

---

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

---

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

풀이

x를 1로 만들기 위한 연산 횟수의 최솟값을 구하기 위해서는
각x/2, x/3, x-1를 1로 만들기위한 연산 횟수 중 가장 작은 값 +1 이다.

이를 재귀함수로 구현하면 불필요한 함수 호출이 자주 발생하므로 메모이제이션을 이용하여 해결했다.
memo 배열을 만들고 인덱스x 위치에 f(x) 값을 저장해둔다.
만약 memo에 이미 f(x)값이 저장되어 있다면 불필요하게 재귀함수를 호출하지 않아도 된다.

f(x/2)과 f(x/3)은 x가 2의 배수, 3의 배수가 아니라면 계산이 불가능하므로 계산 가능한 경우와 그렇지 않은 경우를 나누어야 한다.
x-1은 항상 계산이 가능하므로 f(x-1) 초기값으로 두고 f(x/2)와 f(x/3)의 값을 비교하며 최솟값을 찾는다.
이렇게 하면 memo의 초기값을 고민하지 않아도 된다.

코드

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

using namespace std;

vector<int> memo(1000001, 0);

int dp(int x){
    // cout << x << endl;
    if (x == 1) return 0;
    else if(memo[x] != 0) return memo[x];
    else{
        memo[x] = dp(x-1) + 1;      
        if (x % 2 == 0) memo[x] = min(memo[x], dp(x / 2)+1);
        if (x % 3 == 0) memo[x] = min(memo[x], dp(x / 3)+1);
        return memo[x];
    }
}

int main(){
    int x;
    cin >> x;
    cout << dp(x) << endl;
    return 0;
}