c++ – Code A Primitive Calculator ( x3,x2,+1) Using Dynamic programming

Question -You are given a primitive calculator that can perform the following three operations with the current number 𝑥: multiply 𝑥 by 2, multiply 𝑥 by 3, or add 1 to 𝑥. Your goal is given apositive integer 𝑛, find the minimum number of operations needed to obtain the number 𝑛
starting from the number 1.

ll n;
cin>>n;

vector<ll>vec;
vec.pb(n);

if(n==1)
{
    cout<<0<<endl<<1;
}

else
{
    while(n!=1)
    {
        if(n%3==0)
        n=n/3;
        else if(n%2==0)
        n=n/2;
        else
        n=n-1;
        
        vec.pb(n);
    }
    
    cout<<vec.size()-1<<endl;
    
    for(int i=(vec.size()-1);i>=0;i--)
    cout<<vec(i)<<" ";
}
return 0;

}

for input 96234 iam getting

15

1 2 4 5 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234

but the optimal soln is

14

1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234

i know i am going wrong at the step when 10 is converted into 5 in my code but it should convert it in to 9, Please help me,