[프로그래머스] 파이썬 문제풀이 - 숫자 변환하기

첫 풀이

1. DFS와 BFS로 풀었더니 시간초과가 났다 너무 쉽게 풀긴했다

2. 가지치기가 필요한데 더이상 해줄게 없다

 

def solution(x, y, n):
    def DFS(x,l):
        global cnt
        if x==y and cnt>l:
            cnt=l
        if x>y:
            return
        DFS(x+n,l+1)
        DFS(x*2,l+1)
        DFS(x*3,l+1)
    
    if x%2==0 and y%2==1 and n%2==0:
        return -1
    
    global cnt
    cnt=9999    
    DFS(x,0)
    if cnt==9999:
        return -1
    else:
        return cnt

from collections import deque
def solution(x, y, n):
    answer = 0
    q=deque()
    q.append((x,0))
    while q:
        tmp=q.popleft()
        if tmp[0]==y:
            return tmp[1]
        if tmp[0]<y:
            q.append((x+n,tmp[1]+1))
            q.append((x*2,tmp[1]+1))
            q.append((x*3,tmp[1]+1))
    
    return -1

 

더 나은 답안

1.  y에서 거꾸로 내려가는 방법이다

2. 거꾸로 내려가면 2와3으로 안나눠질때는 큐에 추가해줄 필요가 없어진다

def solution(x, y, n):
    answer = 0
    q=[]
    q.append((y,0))
    while q:
        tmp=q.pop(0)
        if tmp[0]==x:
            return tmp[1]
        if tmp[0]>x:
            if tmp[0]%3==0:
                q.append((tmp[0]/3,tmp[1]+1))
            if tmp[0]%2==0:
                q.append((tmp[0]/2,tmp[1]+1))
            q.append((tmp[0]-n,tmp[1]+1))
            
    return -1

 

배운 점

1. DFS와 BFS를 풀 때 하향식도 생각을 해야겠다

2. 곱하는 연산이 있다면 하향식으로 할때 연산이 줄어든다