[백준 16953] A → B

문제

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

16953번: A → B

---

아이디어

A에서 B로 가는 Bottom-up 방식보다는 B에서 A로 가는 Top-down 방식이 더 편하다. 

왜냐하면, A에서 B로 갈 때는 2를 곱하는 연산, 1을 수의 가장 오른쪽에 추가하는 연산이 모두 가능하기 때문에

모든 조합을 고려하면서 가야한다. (적고 보니 bfs로 가능하려나,, 고민해봐야겠다.)

 

반대로 B에서 A로 갈 때는 매 step마다 한 가지의 경우밖에 없다. 

예제 입력 1을 예로 들어보자. A = 2, B = 162이다. 

→

1. Bottom up 

• 2 → 4도 가능하고, 2→21도 가능하다.
  • 2→4→8도 가능하고, 2→4→41도 가능하다.
  • 2→21→42도 가능하고, 2→21→211도 가능하다.
• n개의 step을 고려하면 2^n가지의 경우가 생기는데, 이를 모두 고려해야 한다. 

2. Top down

• 162→81만 가능하다.
• 81→8만 가능하다.
• 8→4만 가능하다.
• 4→2만 가능하다. 

이제 반례를 찾아보자. 1. A = 3, B = 182, 2. A = 3, B = 262라고 해보자.

• 182→91→9→?
  • 9가 되는 순간 아무것도 할 수 없다. 끝자리가 1도 아니고, 짝수도 아니기 때문이다. 
  • 그러면 이렇게 되는 경우는 loop를 탈출하고 -1을 반환해야 한다. 
• 262→131→13→?
  • 13에서도 아무것도 할 수 없다.

한 자리 수의 경우 끝자리에 1을 빼는 연산을 할 수 없기 때문에 굳이 두 가지로 나눠서 살펴봤지만 결론은 B가 끝자리가 1이 아닌 홀수면 아무것도 못 한다는 뜻이다. 이 상황을 가정하지 않으면 무한루프에 빠지게 된다.

여기서 1인 경우,

b = int(str(b)[:-1])

위의 연산을 사용하게 되면 반환되는 값이 없어지지만, 걱정할 필요가 없는 게 while문은 b가 a보다 클 때 수행되고, 

a는 1보다 크거나 같기 때문에, b가 1이면 while문이 수행되지 않는다.

 

마지막으로,

B가 A와 같아지면 그 때까지의 count에 1을 더한 값을 반환해준다. 

 

반복문이 끝났는데도 A와 B의 값이 다르면, B에서 A로 갈 수 있는 방법이 없다는 뜻이기 때문에 -1을 반환해준다. 

 

---

Solution

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

cnt = 0

# B가 A보다 큰 경우 B를 줄여나감
while b > a :
    cnt += 1
    # B의 가장 오른쪽 수가 1인 경우, B가 1이면 안 됨
    if  str(b)[-1] == '1' : 
        b = int(str(b)[:-1])
    
    # B가 짝수인 경우
    elif b % 2 == 0 : 
        b //= 2
        
    # 1. B의 가장 오른쪽 수가 1이 아닌 홀수
    # 2. B가 10보다 작은 홀수
    else : 
        break
    
if a == b : 
    print(cnt+1)
else : 
    print(-1)