[백준] 16953번 : A → B (파이썬)

문제

나의 답안

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

while True:
    if a==b:#a와 b가 같으면 종료
        break
    elif b<a or (b%10!=1 and b%2!=0):#만들 수 없는 경우
        cnt=-1
        break
    else:#가능한 연산의 두가지 경우
        if b%10==1:#1의 자리가 1인 경우
            b//=10
            cnt+=1
        elif b%2==0:#2로 나눠지는 경우
            b//=2
            cnt+=1
print(cnt)

접근 방법

• 문제를 풀 때에는 a를 b로 만들기보단(bottom up) b를 a로 만들기(top-down)으로 접근해주어야 한다.
• 따라서 2를 곱한다. -> 2로 나눠지면 2로 나눔
• 1을 수의 가장 오른쪽에 추가한다. -> 1의 자리가 1이면 1을 제거
• b를 a로 만들 수 없으면 -1을 해준다. b를 a로 만들 수 없는 경우는
  1. a가 더 크거나
  2. 2로 나누어지지 않고 일의자리가 1이 아니라면 2가지 경우로 나눌 수 있다.