[알고리즘] 백준 16953 파이썬 - A->B

 

16953번: A → B

문제

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

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

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

 

문제풀이

a,b=map(int,input().split())
x=1
#01
while a!=b:
    x+=1
    tmp=b
    #02
    if b%10 ==1:
        b//=10
    elif b%2==0:
        b//=2
    #03
    if tmp == b:
        print(-1)
        break
#04
else:
    print(x)

문제는 a를 b로 바꾸는 것을 원했지만, 나는 b를 a로 바꾸는 것을 선택했다.

- #01 : x 값, 즉 답으로 출력할 값은 횟수+1이기에 1부터 시작한다.

           tmp에는 b를 저장하고 while문은 a와b가 같으면 정지한다.

- #02 : b의 일의 자리가 1이라면 b를 10으로 나눈 나머지를 저장한다.

           즉 일의 자리 1을 없애준다. (1을 수의 가장 오른쪽에 추가하는 과정의 역연산)

           또는 b가 짝수라면 2로 나눈 값을 b에 저장한다.

- #03 : 만약 tmp와 b가 같은 경우, 즉 무한 루프에 빠진 경우는

            -1를 출력하고 break 한다.

- #04 : 문제 없이 종료되었다면, x를 출력한다.