[백준] A → B

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

16953번: A → B

그리디 알고리즘을 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

a, b를 입력받아 a에 

 

1. 2를 곱한다

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

 

이렇게 두가지 연산을 통해 만드는 최소횟수 + 1을 return해야 합니다. 만약 만들 수 없을 경우, -1을 return해야 합니다.

 

<Solution>

간단한 풀이와 주의해야하는점 하나만 이야기하려 합니다.

 

우선 문제의 아이디어는 거꾸로 생각하면 됩니다.

 

ex) 2 → 4 → 8 → 81 → 162

의 경우에서

162가 결국 어떤 수로부터 나왔어야 하므로, 위의 두가지 연산중 이전의 연산은 무조건 2로 나누는 연산이었을 것입니다. 

다음으로 81의 경우 2로 나누어 떨어지지 않으므로 1을 수의 가장 오른쪽에 추가하는 연산이었을 것입니다.

 

이처럼 2의 배수라면 2로 나누어주고, 끝자리 숫자가 1이면 1을 떼어주면서 B에서 A로 만들어 나가면 됩니다. (이것이 성립하는 이유는 1,2가 동시에 가능한 경우가 절대 존재하지 않기 때문)

 

구현을 할 때 주의해야하는 점은 그러면, 

 

"2로 나누어지면 나누고, 1을 뗄수 있으면 떼고, 둘다 안되는 경우, -1을 print하자! "

여기에 사실 하나의 문제점이 있습니다. 

1을 떼어냈는데 0이 되어버리면 2로 무한히 나누어지는 loop에 빠지는 것을 주의해야합니다. 

 

ex) 22->11->1->0

 

이 점만 주의해서 코드를 구현하면 됩니다.

실제 구현은 아래와 같습니다.

import sys

A, B = list(map(int, sys.stdin.readline().rstrip().split()))
times = 0
while(1):
    if B == A:
        print(times+1)
        break
    if B == 0:
        print(-1)
        break
    if B % 10 == 1:
        B = B//10
    elif B % 2 == 0:
        B = B//2
    else:
        print(-1)
        break
    times+=1