숫자 변환하기 - 파이썬(Python)

문제 링크

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 해주세요.

---

제한사항

• 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

---

입출력 예 설명

입출력 예 #1 -> x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2 -> x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3 -> x를 y로 변환할 수 없기 때문에 -1을 return합니다.

---

풀이 과정

• BFS도 가능하고 DP로도 가능한 문제
  • 필자의 문제풀 때 의식의 흐름은 아래와 같다.
  • 보통은 BFS(완전탐색)으로 시작을 한다.
  • 그리고 pruning(백트래킹)을 진행한다.
  • 그래도 시간초과나거나 안풀린다면? 다른 방법을 생각해야 한다. (ex. DP)
• 아래 코드에 위를 대입해보면...
  • BFS로 진행
  • 중복 제거를 통해 pruning
  • 시간 safe ! 
    • safe하지 않았다면 다른 방법을 생각했을 듯.

정답

from collections import deque
def solution(x, y, n):
    answer = -1
    
    q = deque()
    
    q.append((x, 0))
    
    visited = set()
    
    while q:
        value, cnt = q.popleft()

        if value == y:
            answer = cnt
            break

        if value*3 <= y and not value*3 in visited:
            visited.add(value*3)
            q.append((value*3, cnt+1))
        if value*2 <= y and not value*2 in visited:
            visited.add(value*2)
            q.append((value*2, cnt+1))
        if value+n <= y and not value+n in visited:
            visited.add(value+n)
            q.append((value+n, cnt+1))
            
    return answer