[BAEKJOON][python] 백준 온라인 저지 문제 풀이 - 16953번: A → B

문제 링크

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

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

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

입력
첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.

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

소스코드

a, b = map(int, input().split())
count = 1 #필요한 연산의 최솟값에 1을 더한 값을 출력해야 하므로 count를 1로 지정

while b > a : #가능한 연산을 거꾸로 진행하면서 b가 a보다 작거나 같아질 때까지 반복 
    count += 1 #연산 한 번 시행 시 count에 1을 더함
    if b % 2 == 0: #b가 짝수라면 b를 2로 나눈 몫으로 갱신
        b = b // 2
    elif b % 10 == 1 : #b의 일의 자릿수가 1이라면 b를 10으로 나눈 몫으로 갱신
        b = b // 10
    else : #둘 다 해당되지 않는 홀수라면 b를 a로 변경할 수 없으므로 count를 -1로 갱신하고 반복문 종료
        count = -1
        break

if a > b : #가능한 연산을 모두 시행했음에도 b와 a가 같아지지 않았다면 count를 -1로 갱신
    count = -1

print(count)

이 코드의 핵심은
A → B 과정에서는 가능한 연산이 2가지라서 경우의 수가 많아지지만
B → A 과정에서는 가능한 연산이 정해져 있습니다
(ex. B가 짝수라면 그 전 과정에서 2를 곱하는 연산을 한 것임)
따라서 if문으로 B를 검사하여 어떤 연산을 진행해왔는지를 찾고
그 과정을 되돌려서 B를 다시 A로 만들면서 count를 갱신하였습니다