[Baekjoon] 4연산

문제

정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오.

사용할 수 있는 연산은 아래와 같다.

1. s = s + s; (출력: +)
2. s = s - s; (출력: -)
3. s = s * s; (출력: *)
4. s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능)

입력

첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 109)

출력

첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다.

연산의 아스키 코드 순서는 ‘*’, ‘+’, ‘-‘, ‘/’ 이다.

예제

Example 1:

Input: 
7 392
Output: 
+*+

Example 2:

Input:
7 256
Output:
/+***

Example 3:

Input:
4 256
Output:
**

Example 4:

Input:
7 7
Output:
0

Example 5:

Input:
7 9
Output:
-1

Example 6:

Input:
10 1
Output:
/

조건

시간 제한 : 2초

메모리 제한 : 512 MB

풀이과정

풀이 1

from collections import deque
import sys

s, t = map(int, input().split())

if s == t:
    print(0)
    sys.exit()

ans = ""

q = deque()

q.append((s, ""))

MAX = 1000000000

visited = set([s])

while q:
    x, cal = q.popleft()

    if x == t:
        print(cal)
        sys.exit()

    # 4가지 연산 수행
    # 곱하기
    nx = x**2
    if 0 <= nx <= MAX and nx not in visited:
        visited.add(nx)
        q.append((nx, cal+"*"))
    # 더하기
    nx = 2*x
    if 0 <= nx <= MAX and nx not in visited:
        visited.add(nx)
        q.append((nx, cal+"+"))
    # 빼기
    nx = 0
    if 0 <= nx <= MAX and nx not in visited:
        visited.add(nx)
        q.append((nx, cal+"-"))
    # 나누기
    if x != 0:
        nx = 1
        if 0 <= nx <= MAX and nx not in visited:
            visited.add(nx)
            q.append((nx, cal+"/"))

print(-1)