[백준-파이썬] 14395: 4연산

문제 보러 가기!

간단 문제 소개 ✅

정수 s가 주어지는데, 이걸 t로 바꾸는 최소 연산 횟수를 구하는데, 가능한 방법을 출력해야 한다.
s+s, s-s, s/s, s*s 연산을 사용할 수 있다.
바꿀 수 없는 경우도 존재한다.

아이디어 😄

최소 연산 횟수를 구하는 것이고, 가능한 방법이 여러 가지일 때 사전 순으로 앞서는 것을 먼저 출력해야 한다. => BFS 로 풀어야겠다고 생각했다.

그리고 s + s 는 2*s이고, s-s는 0이고, s*s는 s**2이고, s/s는 1이다.

이걸 좀 더 보다 보니까 -는 고려할 필요가 없다.라는 것을 알 수 있었다.
빼기하면 0이 되는데, t는 0보다 크다. 0이 되면 나누기는 불가능하고 더하기, 곱하기, 빼기해도 0이 된다. 그러니까 빼기를 해서는 전혀 답이 될 수 없으니까 고려할 필요가 없다.

좀 더 생각해보니(사실 예제를 관찰해보니까 2의 제곱수가 많아서), 나누기를 해야 답이 되는 경우(s가 t보다 작고, t가 1이 아닐 때. 그리고 뭔가 조건이 더 있는데 이걸 정확히 파악을 못했다.ㅠㅠ )에는 무조건 2의 제곱수만 된다는 것을 알았다. 그래서 이걸 활용해서 뭔가를 해보고 싶었지만, 틀렸다.ㅠㅠ (주석 처리한 부분에서 그 흔적을 볼 수 있다..)

만약에 항상 s를 t로 바꿀 수 있다면,그냥 BFS 돌리면 될텐데..
바꿀 수 없는 경우가 존재한다고 해서, 언제까지 BFS를 돌려야 하는지 고민했다.

그러다가 백준의 질문 검색을 봤더니, t가 10의 9승까지니까 그걸 기준 삼아서 BFS하면 된다는 것을 알았다.

그리고 s==t일 때, t==1일 때(/ 한 번만 하면 되니까)는 답이 명확하니까 먼저 다뤘다.

같은 정수를 또 q에 넣으면 안되니까 방문 체크를 해주고!
이때 방문 체크를 set으로 해줬다.(백준 질문 검색에서 아이디어를 얻었다..ㅎㅎ set으로 방문 체크해줄 수 있다는 것을 새로 알게 되었다! ) 방문한 정수를 set에 넣었고, 더하기, 나누기, 곱하기한 정수가 set에 있는지 확인한 후에 q에 넣었다. list가 아니라 set으로 in을 하면, O(1)만 걸린다고 한다 !

코드 👩‍💻

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)

#
# elif math.log(t, 2) == int(math.log(t, 2)):  # 2의 제곱수
#     cnt = 0
#     n = 2
#     while True:
#         n = n * n
#         cnt += 1
#         if n == t:
#             break
#
#     print('/' + '+' + '*' * cnt)
# else:
#     print(-1)