[백준/Python] 16953_A→B_Python 풀이

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

16953번: A → B

A→B

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2초	512 MB	19415	8164	6522	40.679%

문제

---

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

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

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

 

입력

---

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

 

출력

---

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

 

예제 입력1

---

2 162

2 → 4 → 8 → 81 → 162

예제 출력1

---

5

예제 입력2

---

4 42

예제 출력2

---

-1

예제 입력3

---

100 40021

100 → 200 → 2001 → 4002 → 40021

예제 출력3

---

5

풀이

---

1. 문제에서는 A->B로 가는 것을 목표로 하였지만, 문제를 해결할 때 경우에는 B->A로 가는 것으로 계산의 역순으로 해결하였다. 따라 A와 B가 같아지면 계산의 횟수를 출력하도록 하였다.

 

2. '2로 곱한다'의 역연산인 '2로 나눈다'가 이뤄지면 횟수가 1 증가하도록 하였으며, 2로 나눠지지 않을경우 10으로 나눴을 때, 나머지 일의 자리가 1일 경우 '1을 수의 가장 오른쪽에 추가한다'를 사용한 경우가 되므로 나눈 경우에 일의 자리가 1이 되는 경우 1을 제거하고 횟수가 1 증가하도록 하였다.

 

3. 2번의 연산을 통해서 B가 A로 갈 수 없다면, 이는 A가 B로 갈 수 없는 경우이므로 만들수 없는 경우인 -1을 출력하도록 하였다. 또한 위의 연산에 오류가 발생하는 경우에도 A가 B로 갈 수 없는 경우이므로 -1이 출력되도록 하였다.

 

A,B = map(int, input().split()) #입력 받는 값 

cnt = 1                            #A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값이니, 연산의 최솟값은 1

while True:                        #B->A가 나올때까지 무한 루프

  try:          

    if A == B:                     #A와 B가 같은 경우, 연산횟수 출력

      print(cnt)

      break

    else:                            #A와 B가 같지 않을 경우, 연산 시작

      if B%2==0:                 #B가 2로 나눠지면, A에서 B로 갈 때 2로 곱한 경우의 연산의 경우

        B = B//2                  #B는 B를 2로 나눴을 때의 정수 부분의 몫

        cnt += 1                  #연산횟수 1 증가

      elif B%10 == 1:           #B의 일의 자릿수 확인, 1일 경우 A에서 B로 갈때 가장 오른쪽에 1이 추가된 연산의 경우

        B = int(str(B)[:-1])       #B를 str형으로 변환 후, 가장 끝의 자리 제거하고 다시 int형으로 

        cnt += 1                  #연산횟수 1증가

      else:                          #위의 경우가 이뤄지지 않을경우 A->B로 갈 수 없는 경우

        print(-1)                   # -1을 출력

        break

  except:                           #위의 경우에서 오류가 발생했을 경우 역시 -1을 출력

    print(-1)

    break

---

#sys를 이용하여 입력한 경우

import sys  

A,B = map(int, sys.stdin.readline().split())

cnt = 1

while True:

  try:

    if A == B:

      print(cnt)

      break

    else:

      if B%2==0:

        B = B//2

        cnt += 1  

      elif B%10 == 1:

        B = int(str(B)[:-1])

        cnt += 1

      else:

        print(-1)

        break

  except:

    print(-1)

    break

---