[백준] 파이썬 16953번 A → B 풀

문제 설명

링크

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

문제

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

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

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

 

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

 

출력

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

 

예제입력

 

2 162

 

5

2 → 4 → 8 → 81 → 162

4 42

-1

100 40021

5

 

문제 풀이

아이디어

b가 a로 될 때까지 두 가지 연산을 번갈아 진행한다.

연산을 진행할 수 있는 경우는 다음과 같다.

1. b가 2로 나누어지는 수이거나

2. b의 끝 수가 1이거나

 

1번의 경우 2로 나눈 나머지가 0인 경우고,

2번의 경우 10으로 나눈 나머지가 1인 경우다.

처음에는 2번의 조건을 b%2!==0으로 했는데, 그런 경우에는 다른 홀수로 끝났을 때도 연산을 진행해서 오류가 생긴다.

 

b의 1을 떼주기 = 1을 떼면서 자리수가 한자리 내리기

이렇게 while문을 도는데 while문 조건으로 a와 b가 같지않을 때까지 그리고 b가 a보단 커야 한다. 

 

그리고 result=1을 준 이유는 a가 b가 되는 순간도 카운트에 넣어야 하기 때문이다!

 

풀이

a,b= map(int,input().split())

result=1
while(a!=b and b>a):
  if(b%2==0):
      b=b//2
      result+=1
  elif(b%10==1):
    b= (b-1)//10
    result+=1
  else: break
  
if(b!=a): result=-1
print(result)

 

배운 점.

1을 뗄 때 처음에 문자열로 바꾸었다가 슬라이스로 빼고, 다시 정수로 바꿔주는 번거로운 방식을 썼다.

간단한 연산으로 할 수 없는지 먼저 생각을 해보자!

분기문을 쓸 때, 경우의 수를 잘 생각해보아야 한다.