[백준] 16953 A->B (파이썬 Python)

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

16953번: A → B

문제 설명

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

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

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

---

풀이 과정

• 나의 풀이

① 아이디어 열기

  처음에는 '[백준] 1463 1로 만들기'문제와 형태가 비슷한 거 같아 DP문제이겠다고 생각했지만...!! 전혀 그렇지 않았다...!!

  문제 조건에 의해 A라는 수를 B라는 수로 만들어야한다.

  방법은 크게 2가지인 것같다. A라는 수를 B라는 수로 만드는 과정 혹은 B라는 수를 A라는 수로 만드는 과정에서 답을 찾아야할 것이다.

  이번 풀이는 B라는 수를 A라는 수로 만드는 과정에서 답을 찾을려고 한다. 

  조건에 의해 B가 2로 나누어지는 경우는.... 2의 배수이기만 하면 된다..!! 하지만 1을 빼고 10으로 나누는 경우는.. 10으로 나누었을 때 나머지가 1인 경우이다. 이로써 2가지 조건에 대한 해결법을 대충 찾았다. 우선시 되는 과정은 10으로 나누었을 때 나머지가 1인 경우가 우선시 될 것이다.

 

② 코드 구현

# 16953 A->B
import sys
input = sys.stdin.readline

A, B = map(int,input().split())
result = 1

while True :
    if A == B :
        break
    elif (B % 2 != 0 and B % 10 != 1) or (B < A) :
        result = -1
        break
    else :
        if B % 10 == 1 :
            B = B // 10
            result += 1

        else :
            B = B // 2
            result += 1

print(result)

  B가 2로 나누어지지 않고 10으로 나누었을 때 1이 아니면 에초에 결과값을 -1로 정하고, 또한 B가 A보다 작으면 결과값을 마찬가지로 -1로 정한다.

---

후기

  여러가지 해결방법이 떠오를 때.. 그중 한가지 방법에만 매몰되지 않는 것이 중요한 것같다...!!