정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
첫째 줄에 A, B (1 ≤ A < B ≤ )가 주어진다.
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
2 162
5
나머지 예제는 생략한다.
import sys
input = sys.stdin.readline
a,b = map(int,input().rstrip().split())
answer= -1
def go(s,e,c):
global answer
if s == e:
answer = c
return
if s>e:
return
else:
go(s*2,e,c+1)
go(s*10+1,e,c+1)
return
go(a,b,0)
if answer > 0 :
print(answer+1)
else:
print(answer)
백트래킹
을 이용해 문제를 해결했다.B
보다 커지는 경우에는 더 탐색하지않고 return 시킨다.BFS
와 DP
로도 문제를 해결할 수 있을 거 같은데 추후에 해봐야겠다.