백준 16953 문제
백준 16953 풀이
나는 아직 BFS나 DFS를 배우지 않았기에 그냥 단순한 방법으로 풀었다. A->B를 거슬러 올라가는 것이 아니라, B->A로 반대로 생각한 것이다.
만약 A->B로 만들 수 있는 숫자라면, B는 2로 나눠지거나(나머지 0), 끝자리가 1이어야 한다. 만약 2로 나눈 나머지가 0이 아니거나, 혹은 계속 나눴더니 B가 A보다 작아진다면 -1을 출력하면 된다.
#16953
# sys 연습
import sys
# 입력
A, B = sys.stdin.readline().split()
# B를 반복 돌리기
cnt = 1
while True:
if int(A)>int(B):
print(-1)
break
elif int(A) == int(B):
print(cnt)
break
elif str(B)[-1]== '1':
B = str(B)[:-1]
cnt+=1
elif int(B)%2==0:
B = int(int(B)/2)
cnt+=1
else: # 끝자리가 3,5,7,9 뭐 이렇게 끝나서 2로 나눈 나머지가 0이 아닌 경우
print(-1)
break
No Responses