[백준] A->B 16953번 (python)

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

16953번: A → B

풀이 방법

처음엔 bfs로 풀었는 데 시간이 초과 났다.

그래서 그리디로 접근했다. 

그리디는 보통 뒤에서부터 해결한 경험이 있어 A->B구하는 거 보단 B->A로 구해야겠다고 생각했다.

하지만 예제 정답 부분만 보고 짝수이면 나누기 2 홀수이면 -1 후 나누기 10을 했다. 

예시 부분은 다 정답처리가 되었지만 1 25같은 수가 입력된다면 제대로 해결하지 못할 것이다.

그래서 10으로 나누었을 때 나머지가 1인 경우, 2로 나누었을 때 나머지가 1인 경우 다른 경우는 실패 이렇게 3가지 경우로 나누게 되었다.

A, B = map(int, input().split())
cnt = 0
while True:
    if (A > B): ## 실패 경우
        cnt = -1
        break
    if(A == B): ## 성공 경우
        cnt += 1
        break
    if(B % 10 == 1): ## -1 후 10으로 나누어 지는 경우
        B -= 1
        B = B // 10        
    elif(B % 2 == 0): ## 2로 나누어 지는 경우
        B = B // 2
    else:         ## 실패
        cnt = -1
        break
    cnt += 1
print(cnt)