Maybe generate all natural x and y such that $$$2^x 3^y \leq n$$$. There exist only $$$O(log^2(n))$$$ such pairs. Get the minimum cost seeing the solution generated by each pair.

UPD: Not always the optimal strategy. By seeing the editorial provided in the comments below, it seems we should start backwards and either decrease until zero or decrease until find a multiple of 2 or 3 of the form $$$k \ floor(\frac{n}{k})$$$ or $$$k \ ceil(\frac{n}{k})$$$. So the solution is always of the form $$$\sum c_i + \sum 2^{a_j} 3^{b_j}$$$.

I was mistaken I didn't see the contraints

I guess you can simply use recursion. Just keeping check of the usage of +1/-1 will not give TLE. Something like this:

def cost(curr):
    if curr == 0:
        return 0 
    if curr%2!=0 and curr%3!=0:
        return cost(curr - 1) + r
    ans1,ans2 = 10**18,10**18
    if curr%2==0:
        ans1 = cost(curr//2) + p 
    if curr%3==0:
        ans2 = cost(curr//3) + q
    return min(ans1,ans2)
    
    
n = 10**18
p = 1
q = 2 
r = 8 
print(min(cost(n),cost(n+1)+r))

This problem was asked in previous Atcoder round. i am sharing the link below

Problem Link : Pay to Win

Editorial : this