✏️ 14395번

문제

💡 문제 아이디어

• queue 를 이용할 때 정수 와 해당 정수까지의 연산 문자열 을 튜플 형식으로 저장한다
• t가 1이상이기도 하고 0은 + , * , / , - 를 해도 같은 0이 나오기 때문에 - 는 고려하지 않는다
• s,t 가 1이상 1000000000 이하 이므로 연산 결과가 1000000000 초과로 나온 값은 고려하지 않는다

👀 풀이

# 14395

import sys
from collections import deque

s,t = map(int, sys.stdin.readline().split())

def cal(s, num) :
    if s == '*' :
        return num*num
    elif s == '+' :
        return num+num
    elif s == '/' :
        return 1
    else :
        return


if s==t :
    print(0)
elif t == 1 :
    print('/')
else :
    visited = set()
    ans = -1
    q = deque()
    q.append((s,''))
    while q :
        qh_num , qh_method = q.popleft()
        if qh_num == t :
            ans = qh_method
            break
        for i in ['*' , '+' , '/'] :
            nxt = cal(i,qh_num)
            if nxt <= 10**9 and nxt not in visited :
                q.append((nxt, qh_method+i))
                visited.add(nxt)

    print(ans)

• 다른 풀이들을 참고하여 방문 처리를 set() 을 이용하였다 (set을 이용하면 O(1) 만 걸리기 때문 !!)