[Python/Programmers] 숫자 변환하기

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

프로그래머스

문제 설명

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

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

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

풀이(BFS)

Code(BFS)

from collections import deque
def solution(x, y, n):
    # 1. 방문 여부 리스트 생성
    visited = [False] * (y+1)
    # 2. 큐에 (현재 위치, 0) 삽입
    queue = deque()
    queue.append((x, 0))
    # 3. 현재 위치 방문 처리
    visited[x] = True
    # 4. 
    while queue :
        # 4-1. 위치, 연산 횟수 반환
        x, count = queue.popleft()
        # 4-2.
        for nx in [x+n, 2*x, 3*x] :
            # 4-2-1. 예외처리
            if nx > y : continue
            # 4-2-2. 방문하지 않은 경우
            if not visited[nx] :
                # y 값에 도달할 경우
                if nx == y : return count + 1 # 연산횟수 + 1 반환
                else :
                    # 방문 처리
                    visited[nx] = True
                    # 큐에 (다음 위치, 연산 횟수 + 1) 삽입
                    queue.append((nx, count + 1))
    # 5. x와 y 가 같은 경우 0 반환, 이외의 경우 -1 반환
    return -1 if x != y else 0

풀이(DP)

Code(DP)

def solution(x, y, n):
    INF = float('inf')
    # 1. DP 생성
    dp = [INF] * 1_000_001
    # 2. 초기값 설정
    dp[x] = 0
    # 3.
    for i in range(x, y+1) :
        # 현재 인덱스에 값이 있을 경우
        if dp[i] != INF :
            for nx in [n + i, 2 * i, 3 * i] :
                # 예외 처리
                if nx > y : continue
                # 최솟값 업데이트
                dp[nx] = min(dp[nx], dp[i] + 1)
    # 4. 결과 리턴
    return -1 if dp[y] == INF else dp[y]