문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다

• x에 2를 곱합니다.

• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요

BFS 풀이

from collections import deque

def solution(x, y, n):
    if x == y :
        return 0
    
    #BFS 풀이
    q = deque([(x,0)])
    visited = [False]*(y+1)
    visited[x]=True
    
    while q :
        cur,cnt= q.popleft()
        
        for nxt in (cur+n, cur*2, cur*3):
            if nxt > y :
                continue
            
            if not visited[nxt] :
                if nxt == y :
                    return cnt + 1
                
                visited[nxt] = True
                q.append((nxt, cnt+1))
        
    return -1

DP 풀이

from collections import deque

def solution(x, y, n):
    INF = float('inf') # 무한대
    dp = [INF] * (y+1)
    dp[x] = 0
    #dp[i] : i 까지 가는 최소 횟수
    for i in range(x+1, y+1):
        
        if i-n >= x :
            dp[i] = min(dp[i], dp[i-n]+1) # 현재 값이나 이전값에서 1번 이동
        if i%2 == 0 and i//2 >= x : 
            dp[i] = min(dp[i], dp[i//2]+1) 
        if i%3 == 0 and i//3 >= x : 
            dp[i] = min(dp[i], dp[i//3]+1) 
    
    
    return dp[y] if dp[y]!=INF else -1