[백준 / BOJ] A → B - 16953 (Python)

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

 
주어진 두가지의 연산을 이용해서 자연수 A를 B로 변환할 때, 필요한 연산 횟수의 최솟값을 구하는 문제이다.
A에서 B로 도달하는 것이 불가능할 수도 있으며, 이러한 경우 -1을 출력한다. (B >  A로 주어진다.)
 

풀이

크게 두가지 방법으로 나눌 수 있다. 문제에서 의도한 풀이는 아마 BFS를 활용한 풀이로 짐작된다. 그러나 그리디한 방법을 사용하면 BFS보다 더욱 빠르게 처리할 수 있다.
 

1.

  지문을 자세히 보면, 두가지 사실을 알 수 있다. 둘 중 어떤 연산을 거쳐도 항상 수는 증가하며, 한번의 연산을 거치면 마지막 자리는 항상 1이거나, 짝수라는 것이다.
 

2.

  위와 같은 사실을 통해 다시 생각해보면, A → B가 아닌, B → A로 이동하는 연산을 적용하면, 두가지의 연산을 다 해볼 필요 없이 한가지의 연산만 사용할 수 있다는 것을 알 수 있다.
  예를 들어 B의 마지막 자리가 짝수라면 2로 나누면 되고, 1이면 1을 제거(1을 빼고 10으로 나눔) 해주면 된다. B에서 한번 연산을 진행하고 나온 B'에 대해서도 같은 연산을 반복하면 결국 A에 도달할 수 있을 것이다.
 

3.

  만약 B'의 마지막 자리가 1이 아닌 홀수라면? A에서 어떤 연산을 해도 B에 도달할 수 없다는 뜻이므로 -1을 출력하면 된다.
 
BFS로 문제를 풀이하면 연산시 두가지 분기로 나누어지지만, 위의 그리디 풀이를 이용하면 항상 최적의 연산을 수행할 수 있다.
 

소스 코드

import sys

a, b = map(int, sys.stdin.readline().split())

"""중요한건 맨 뒷자리? 뒷자리가 0,1,2,4,6,8 이 아니라면 도달하는 것이 불가능함
어떤 수던지 마지막자리가 1이 아니라면 그 전 연산은 2를 곱하는 연산이었을 것이며, 1이라면 1을 수 오른쪽에 추가하는 연산이었을 것이다.
따라서 마지막 자리가 1이면 1을 빼고 10으로 나눈다. 그리고 마지막 자리가 0,2,4,6,8 이면 2로 나눈다. 그 어느것에도 해당하지 않으면 도달할 수 없으므로 -1이다"""

count = 1 # 문제의 지문엔 연산의 횟수라고 적혀있지만, 실제론 노드의 개수를 출력하도록 되어 있기에 1에서 시작.

while True :
    if b == a : break # a에 도달하면 멈추자
    
    elif b < a : # a보다 작아지면 a에 도달할 수 없다
        count = -1
        break
    
    last = b%10 # 마지막 자리
    
    if last == 1 : b = (b-1)//10 # 마지막 자리가 1이면 1을 제거
    
    elif last in [0,2,4,6,8] : b = b//2 # 마지막 자리가 짝수면 2로 나누어 준다.
    
    else : # 마지막 자리가 1이 아닌 홀수면 a에 도달할 수 없다
        count = -1
        break

    count += 1
    
print(count)