[백준/BOJ][Python] 16953번 A → B

[백준/BOJ][Python] 16953번 A → B

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

16953번: A → B

 

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

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

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

예제 입력 1 

2 162

예제 출력 1 

5

2 → 4 → 8 → 81 → 162

예제 입력 2 

4 42

예제 출력 2 

-1

예제 입력 3 

100 40021

예제 출력 3 

5

---

아이디어

거꾸로 생각해야한다.

A에서 B로 가는 걸 생각하는 게 아니라 B에서 A로 간다고 생각해보자.

만약에 B 일의 자리가 1이라면 그 전 과정에서 1을 붙인거고, 1이 아니라면 2배한 것이다

 

1을 붙인거라면 B의 일의자리만 빼고 갱신해준다. 즉 1891이었다면 189로 갱신! 이건 10으로 나눈 몫을 생각하면 된다

+) 1을 붙였다는 것은 10으로 나누었을 때 나머지가 1인 경우이다.

 

2배한 경우면 2로 나눠주면 된다!

 

이렇게 거꾸로 B를 갱신하며 몇 번 계산했는지 세주다가(result) B가 어느 순간 A랑 같아지면 result를 출력하면 되는데

만약 B가 A보다 작아졌다?

그러면 A로 B를 못 만드는 것이므로 -1을 출력해줘야한다!

 

 

 

---

코드

A, B = map(int, input().split())
result = 1
# 거꾸로 생각
while True:
    if (B % 10) == 1: # 일의 자리가 1이면
        B //= 10
    else:
        B /= 2
    result += 1

    if A > B:
        print(-1)
        break

    if A == B:
        print(result)
        break