프로그래머스 - 숫자변환하기 (파이썬)

이 문제는 범위에 제한이 있어야 풀리는 문제이다. dfs나 bfs를 사용하면 depth, width가 무한정 커질 수 있기 때문에 배열을 사용하여 범위에 제한을 두고 for문을 돌려야 한다.

 

 

1. dfs 사용(x)

 

answer=1000000
def dfs(x,n,y,tot,cnt):
    global answer
    if tot>=x:
        if tot==x:
            answer=min(answer,cnt)
            return
        if tot%3==0:
            dfs(x,n,y,tot//3,cnt+1)
        if tot%2==0:
            dfs(x,n,y,tot//2,cnt+1)
        dfs(x,n,y,tot-n,cnt+1)
def solution(x, y, n):
    global answer
    dfs(x,n,y,y,0)
    if answer==1000000:
        return -1
    return answer

 

2. bfs사용(x)

 

def solution(x, y, n):
    que=[[x,0]]
    i=0
    while(i<len(que)):
        tmp=que[i]
        i+=1
        if tmp[0]==y:
            return tmp[1]
        elif tmp[0]<y:
            que.append([tmp[0]*3,tmp[1]+1])
            que.append([tmp[0]*2,tmp[1]+1])
            que.append([tmp[0]+n,tmp[1]+1])
    return -1

 

3. dp 사용

 

MAX = 1_000_000
INF = float('inf')

def solution(x, y, n):
    arr=[INF]*(MAX+1)
    arr[x]=0
    for i in range(x,y):
        if arr[y]!=INF:
            return arr[y]
        for j in (i*2,i*3,i+n):
            if j>MAX:
                continue
            arr[j]=min(arr[j],arr[i]+1)
    return arr[y] if arr[y] != INF else -1