https://www.acmicpc.net/problem/16953
시간 2초, 메모리 128MB
input :
- A, B (1 ≤ A < B ≤ 109)
output :
- 연산의 최솟값에 1을 더한 값을 출력
- 만들 수 없는 경우에는 -1을 출력
조건 :
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
B를 기준으로 제일 뒤에 1이 존재하면 슬라이싱 하고 아니면 2로 나누려 했다.
그러나 이렇게 할 경우 계속 1을 뒤에 추가하는 경우를 잡지 못하게 된다.
결국 재귀적으로 풀자. 이게 언제나 제일 편하다.
import sys
sys.setrecursionlimit(100000)
def dfs(num, count):
global cnt, flag
if num == b:
flag = 1
cnt = min(cnt, count)
return
word = str(num) + '1'
if int(word) <= b:
dfs(int(word), count + 1)
if num * 2 <= b:
dfs(num * 2, count + 1)
a, b = map(int, sys.stdin.readline().split())
flag = 0
cnt = float('inf')
dfs(a, 0)
print(cnt + 1 if flag else -1)
