4연산 풀이

문제 링크: https://www.acmicpc.net/problem/14395

백준 알고리즘 중급 1/3 611에서 16번째 - 14395번 4연산을 풀어보았다.

 

풀이: https://dalseoin.tistory.com/entry/%EB%B0%B1%EC%A4%80-14395-4%EC%97%B0%EC%82%B0

 

C++

 

Python

import collections
import math

s,t = map(int,input().split())
if s == t:
    print(0)
elif t == 1:
    print('/')
else:
    visited = set()
    q = collections.deque()
    q.append((s, ''))
    while q:
        tmp, tmp_method = q.popleft()
        if tmp == t:
            print(tmp_method)
            break
        else:
            if tmp * tmp <= 10**9 and tmp * tmp not in visited:
                q.append((tmp * tmp, tmp_method + '*'))
                visited.add(tmp * tmp)
            if tmp + tmp <= 10**9 and tmp + tmp not in visited:
                q.append((tmp + tmp, tmp_method + '+'))
                visited.add(tmp + tmp)
            if tmp / tmp not in visited:
                q.append((tmp / tmp, tmp_method + '/'))
                visited.add(1)
    else:
        print(-1)

Java