[백준]16953 A->B(Python)

https://www.acmicpc.net/problem/16953

16953번: A → B

 

문제 정리

 

A => B

1. 2를 곱한다.

2. 1을 수의 가장 오른쪽에 추가 

 

1, 2의 연산을 반복해서 A => B로 바꾸는데 필요한 연산의 최솟값 + 1 or -1 출력 

 

문제 접근

 

그리디라는 생각은 들었지만 2번 연산이 좀 까다롭다고 느껴졌다.

 

top-down방식을 사용해 B를 A로 만든다고 가정하면, 

 

일의 자릿수가 1이라면 1을 제거 그렇지 않다면 2로 나누기 

 

코드

 

시간 초과

import sys
input = sys.stdin.readline

cnt = 1

A, B = map(int, input().split())

# 반복문 탈출하려면..?

while B != A:
    if B % 10 == 1:
        B //= 10
    elif B % 2 == 0:
        B //= 2

    cnt += 1
    if B < A:
        print(-1)
        break

if B == A:
    print(cnt)

 

수정

import sys
input = sys.stdin.readline

cnt = 1

A, B = map(int, input().split())

# 반복문 탈출하려면..?

while True:
    if A == B:
        break
    elif A > B:
        cnt = -1
        break
    elif B % 10 == 1:
        B //= 10
        cnt += 1
    elif B % 2 == 0:
        B //= 2
        cnt += 1
    else:
        cnt = -1
        break

print(cnt)