728x90
1. B를 A로 만들어보자!
나는 B->A로 만드는 방법을 떠올렸다
B에서 2로 나눠지면 나누고, B의 맨 마지막 숫자가 1이면 1을 떼어주고,
2로 나눠지지 않고 마지막 숫자 (10으로 나눴을 때 나머지)가 1이 아니면 -1 을 리턴
+ 그런데 여기서, B는 항상 A보다 커야한다 ! 즉 B < A 인 값이 나와도 -1을 리턴한다
a, b = map(int, input().split())
count = 1
while True:
if b == a:
break
elif (b % 2 != 0 and b%10 != 1) or (b < a):
count = -1
break
else:
if b%10 == 1:
b //= 10
count += 1
else:
b //= 2
count += 1
print(count)
2. 사실 BFS로 푸는건 조금 생소했는데..! BFS로도 풀수있다
from collections import deque
a, b = map(int, input().split())
result = -1
queue = deque()
queue.append((a, 1))
while queue:
num, count = queue.popleft()
if num == b:
result = count
break
if num*2 <= b:
queue.append((num*2, count+1))
if int(str(num) +'1') <= b:
queue.append((int(str(num)+'1'), count+1))
print(result)
queue에 (현재값, 계산한횟수)를 넣어준다.
그리고 queue가 빌 때까지 연산한다.
현재 값을 요리조리 2배 하거나 뒤에 1붙여도 b보다 작거나 같으면 연산을 수행하고 , b랑 현재 값이 같아지면 연산 종료한다.
queue가 빌때까지 연산을 수행해도 b와 값이 같아지지 않으면 -1를 출력 !
재밌구만~
728x90
