[백준/BOJ] gold5 - 14395번 4연산 (Python)

▶14395 - 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 ≤ 10^9)

▶출력

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

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

728x90

▶풀이

빼기는 하면 0이 되기 때문에, 다음 연산을 할 수가 없다.

그렇기 때문에 빼기를 제외한 나머지 3개만 처리해 주면 된다.

 

최대 사이즈를 모르기에 그냥 10e9로 처리하고, visit는 set()으로 설정했다.

나머지는 bfs랑 동일하게 하면 돼서 비슷하게 해 주었다.

from collections import deque


def bfs(a):
    queue = deque()
    queue.append((a, ''))
    visit = set()
    visit.add(a)
    MAX = 10e9

    while queue:
        s, op = queue.popleft()

        if s == t:
            return op
        
        ns = s * s
        if 0 <= ns <= MAX and ns not in visit:
            queue.append((ns, op + '*'))
            visit.add(ns)

        ns = s + s
        if 0 <= ns <= MAX and ns not in visit:
            queue.append((ns, op + '+'))
            visit.add(ns)

        ns = 1
        if ns not in visit:
            queue.append((ns, op + '/'))
            visit.add(ns)
    
    return -1


s, t = map(int, input().split())
if s == t:
    print(0)
else:
    print(bfs(s))