💡문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
풀이💬
import sys
from collections import deque
input = sys.stdin.readline
def dfs(x, y):
q = deque([(x,1)])
while q:
now, cnt = q.popleft()
if now == y:
print(cnt)
return
if now *2 <= y:
q.append((now*2, cnt +1))
if now *10+1 <= y:
q.apend((now*10+1, cnt+1))
print(-1)
x, y = map(int, input().split())
dfs(x, y)
'알고리즘 문제' 카테고리의 다른 글
[Python]14395번.4연산(그래프, BFS) (1) | 2023.12.28 |
---|---|
[Python]13549번.숨바꼭질3(그래프,BFS)⭐️ (0) | 2023.12.22 |
[Python]5567번.결혼식(그래프,BFS) (0) | 2023.12.20 |
[Python]2667번.단지붙이기(그래프,DFS,BFS) (1) | 2023.12.19 |
[Python]1697번.숨바꼭질(그래프이론, 그래프 탐색, BFS)⭐️ (0) | 2023.12.18 |