[백준] 16953 A->B

https://acmicpc.net/problem/16953 

16953번: A → B

a, b = map(int, input().split())
result = 1
break_chk = False
while b > a:
    result += 1
    if b & 1 == 0:
        b = b >> 1
    elif b % 10 == 1:
        b //= 10
    else:
        break_chk = True
        break
else:
    if a == b:
        print(result)
    else:
        print(-1)

if break_chk:
    print(-1)

너비 우선 탐색으로 나와있긴한데 시간이 오래걸리지 않을까 생각이 들었다.

그래서 그리디로 풀었다.

 

범위가 1<A<B<=10^9 이기때문에 B를 줄여가는게 더 낫다고 판단했다.

B가 짝수인경우에만 2로 나누어주고(b=b>>1) B의 일의 자리수가 1인경우에만 1을 빼는 식으로 구현했다.

B가 A보다 작거나 같아지면 종료가 되는데 같은 값이면 만들수 있으므로 해당 값을 출력하고, 다른 값인경우 -1을 출력했다.

나머지 경우에는 빼거나 나누지 못하는 경우이므로 break를 걸고 -1을 프린트 해주었다.