문제는 간단하다
A와 B의 값을 받았을때 두가지 연산을 사용해서 최소한의 연산 횟수를 구하는 것이다.
연산 종류
1. 2를 곱한다.
2. 1을 수 가장 오른쪽에 추가한다.두번째 연산은 A X 10 + 1과 같다.
최소한으로 연산을 하려면 당연히 최대한 2번째 연산을 많이 사용하는것이 좋을것이다.
그렇지만 초기 A에서 2번째연산을 사용하면 B에 더 가까워 질 수 있겠지만 B가 될것이라는 근거가 없다.
반대로 생각해보면 두 연산을 B에서 나누는 연산으로 A를 만들수 있다면 근거가 생긴다.
이 아이디어와 비슷한 문제가 있다.
=> [출처] 백준 1로 만들기
두가지 연산을 바꾸면 이렇게 된다.
1. A X 2 == B / 2
2. A X 10 + 1 == (B-1) / 10
이 연산을 사용해서 역으로 답을 찾아내는 방법이다.
a,b = map(int,input().split())
cnt = 1
while a < b:
cnt += 1
if b % 10 == 1: # 홀수이고 뒷자리가 1일때
b = (b - 1) // 10
elif b % 2 == 0: # 짝수일때
b //= 2
else: # 두 조건에 하나라도 걸리지 않으면 만들수 없음
break
print(cnt if a == b else -1)코드 설명
- 2번째 연산을 할때 B의 값의 마지막 자리수는 무조건 1이여야한다.
(1번째 연산은 짝수이면 가능하다)- 두가지 연산에 해당되지 않으면 B를 A로 만들 수 없게 된다.
B의 마지막 자리수가 무조건 1이여야하는 이유를 다른 TestCase를 가지고 설명해보면
A,B = 2, 254
첫번째: 254 / 2 = 127
두번쨰: (127 -1) / 10 = 12.6 ... (?)
B의 맨 뒷자리가 1이 아니기 때문에 뒷자리가 소수로 남아버린다.
그러므로 두 연산에 해당되지 않으면 만들 수 없는 숫자로 반복문을 중단하고
-1을 출력한다.
