백준 14395 파이썬 - 4연산

https://www.acmicpc.net/problem/14395

14395번: 4연산

문제

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

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

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

코드

import sys
from collections import deque
s, t = map(int, sys.stdin.readline().split())
if s == t:
    sys.stdout.write("0")
    exit()
def bfs():
    q = deque()
    q.append((s, ""))
    check = [s]
    operation = ["*", "+", "-", "/"]
    while q:
        num, op = q.popleft()
        if num == t:
            return op
        for i, nextNum in enumerate([num * num, num + num, 0, 1]):
            if nextNum > t:
                continue
            if nextNum not in check:
                q.append((nextNum, op + operation[i]))
                check.append(nextNum)
    return "-1"
sys.stdout.write(bfs())

풀이

연산을 그냥 다 해도 되지만(시간이나 메모리 초과가 날 것 같다) 뺄셈 혹은 나눗셈은 0, 1 만 나오므로 0과 1로 설정하고, t보다 큰 수가 연산되는 경우는 제외시키면서 풀면 좋다.