[프로그래머스|파이썬] 숫자 변환하기 (연습문제/lv.2)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

 

 

🐍파이썬

DFS

def solution(x, y, n):
    def dfs(v, cur):
        global answer
        if cur == y:
            answer = v
            return
        if cur > y:
            return
        dfs(v+1, cur+n)
        dfs(v+1, cur*2)
        dfs(v+1, cur*3)
    global answer
    answer = 0
    dfs(0, x)
    return answer - 1

재귀호출 초과 런타임 에러, 실패 뜬 코드

DP

def solution(x, y, n):
    answer = 0
    ans = set()
    ans.add(x)
    
    while ans:  #더 이상 연산할 숫자가 없을 때까지 반복
        if y in ans:    #ans에 타겟넘버가 있는 경우
            return answer   #연산횟수 리턴
        temp = set()
        for i in ans:   #ans의 각 원소에 대해 3가지 연산 진행
            if i+n <= y:    #y보다 커지면 y가 될 가능성이 없으므로 연산할 목록에서 제외
                temp.add(i+n)
            if i*2 <= y:
                temp.add(i*2)
            if i*3 <= y:
                temp.add(i*3)
        ans = temp  #ans를 temp값으로 갱신
        answer += 1 #연산횟수+1
    return -1

 

 

다른 풀이 방법

BFS

from collections import deque

def solution(x, y, n):
    visited = [0] * 1000001

    q = deque()
    q.append((x, 0))
    visited[x] = 1
    while q:
        num, cnt = q.popleft()
        if num == y:
            return cnt
        for next_num in (num + n, num * 2, num * 3):
            if next_num <= y and not visited[next_num]:
                visited[next_num] = 1
                q.append((next_num, cnt + 1))

    return -1