새싹프로그래머의 이야기

[문제 풀이]

• 연산의 최소 횟수를 구해야하므로 bfs를 활용하였습니다.
• 이때 연산된 값은 y보다 같거나 작아야하며, 거리가 구해진 적이 없어야만 갱신해주었습니다.(거리가 구해졌는지 여부와 상관 없이 값을 구하면 최소 연산 횟수를 구할 수 없습니다.)

[풀이 코드]

from collections import deque


def solution(x, y, n):
    answer = 0
    dq = deque([x])
    distance = [0 for _ in range(1000001)]

    if x == y:
        return 0
    while dq:
        val = dq.popleft()

        if 1 <= val * 2 <= y and distance[val * 2] == 0:
            distance[val * 2] = distance[val] + 1
            dq.append(val * 2)
        if 1 <= val * 3 <= y and distance[val * 3] == 0:
            distance[val * 3] = distance[val] + 1
            dq.append(val * 3)
        if 1 <= val + n <= y and distance[val + n] == 0:
            distance[val + n] = distance[val] + 1
            dq.append(val + n)

    return distance[y] if distance[y] != 0 else -1