이야 오늘 잘 풀리는구만

1. 내 풀이 1: 실패

import sys
input = sys.stdin.readline

a, b = map(int, input().split())
cnt = 0

while a != b:
    if a > b:
        print(-1)
        exit()
    if str(int(b))[-1] == '1':
        cnt += 1
        b = str(int(b))
        len_b = len(b)
        b = int(b[:(len_b-1)])
    if b != int(b):
        print(-1)
        exit()
    else:
        cnt += 1
        b = b/2

print(cnt+1)

완벽하다고 생각했으나 아예 틀렸습니다가 나온 풀이 ^^
저 if b != int(b) 의 구문이 틀린 듯 했다.

그래서 아래처럼 바꾸어 주었다.

2. 내 풀이 2: 성공

import sys
input = sys.stdin.readline

a, b = map(int, input().split())
cnt = 0

while a != b:
    if a > b:
        print(-1)
        exit()
    if str(int(b))[-1] == '1':
        cnt += 1
        b = str(int(b))
        len_b = len(b)
        b = int(b[:(len_b-1)])
    else:
        if b%2 != 0:
            print(-1)
            exit()
        cnt += 1
        b = b/2


print(cnt+1)

2로 나눌 때 만약 나머지가 있다는 말은 소수점이 생긴다는 말이므로!
이 경우 주어진 연산에 의해 a를 b로 만들 수 없다고 생각했다.
(사실 위에랑 비슷한 맥락인 것 같은데 정확히 왜 틀린지는 ... 혹시 아는 분이 있으면 댓글 부탁드립니다!)

3. 다른 풀이

a,b = map(int,input().split())
r = 1
while(b!=a):
    r+=1
    temp = b
    if b%10 == 1:
        b//=10
    elif b%2 == 0:
        b//=2
    
    if temp == b:
        print(-1)
        break
else:
    print(r)

풀이 출처: https://my-coding-notes.tistory.com/210

오호 ... 나처럼 string 만들었다가 integer 만들었다가 생쇼 하는 짓을 하지 않아도 된다!
나머지를 잘 이용하면 됨 ⭐️

이 문제는 bottom-up BFS로도 풀 수 있다고 위 블로그에서 말하고 있는데,
BFS로 풀 때 한 번 도전해봐야겠다! :)

4. 마치며

그리디 ... 이제 슬슬 감이 잡히고 있다!
안 풀릴 것 같을 때 or 도저히 못 풀겠을 때는 마음 속으로

그리디는 조건 ...

이라는 주문을 외치자!