[프로그래머스] 숫자 변환하기 (Python)

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

프로그래머스

Status : Solved

Time : 00:05:01

 

---

 

문제 설명

 

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

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

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

 

입력 및 출력

 

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

 

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

 

 

---

 

풀이

이번 문제는 BFS 문제의 기초라고 볼 수 있겠다. 도달하는 최소 횟수를 구하는 문제는 난이도에 따라 다르겠지만, BFS를 이용하면 더 효율적인 경우가 많다. 큐 자료구조를 활용하면 간단하고, 이미 방문한 숫자를 visited 배열로 체크하는 것도 잊지 말자.

 

풀이 코드

from collections import deque

def solution(x, y, n):
    visited = [float('inf')]*1000001
    q = deque([(x, 0)])
    
    while q :
        num, cnt = q.popleft()
        if num == y :
            return cnt
        if num > 1000000 or visited[num] <= cnt :
            continue
        visited[num] = cnt
        
        q.extend([(num*2, cnt+1), (num*3, cnt+1), (num + n, cnt+1)])
        
    return -1

풀이 완료~