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

백준 16953 A->B 

 

 

 

📜 문제 

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

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

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

 

 

🚩 입력 

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

 

 

🌞 출력

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

 

 

🥨문제 풀이 

주어진 두 수 a, b 중 a가 ---> b 로 변하는 연산들의 횟수를 출력한다. 주어진 연산은 

1) 2를 곱하기 

2) 수의 끝에 1을 붙이기 (숫자 연산이 아닌 문자열 더하기처럼   23 + 1 = 231 )

a를 요 두 가지의 연산 중 하나를 선택하여 연산을 해 나가다 보면 b가 된다. 이 때 연산 횟수를 출력하는 문제!

 

처음에는  a -> b 방향으로 생각해보니 2개 중 하나를 선택하는 경우의 수가 2의 제곱승으로 무한해지는 느낌이라 감을 잡지 못하다가 반대로 b->a로 생각해보니 답과 가까워질 수 있었다. 

 

먼저 b가 2로 나눠진다면 이전 연산은 1번 (2를 곱하기) 였을 것이고 만약 뒤의 자리가 1이라면 이전의 연산은 2번 (수 끝에 1을 붙이기) 였을 것이다. 만약 2로 나눠지지도 않고 끝의 수가 1도 아니라면 그대로 break 을 하면 된다. 

이렇게 1,2번을 나누어 생각할 수 있는 이유는 2는 짝수, 2의 배수이고 1로 끝나면 짝수 배수가 절대 아니기 떄문에 가능하다. 

 

a가 b보다 작을 동안 만약 b가 짝수이면 2로 나누고 1로 끝나면 1을 빼고 둘 다 아니라면 (~~3, ~~7로 끝나면) break을 한다. 그리고 a==b 로 같아졌다면 이는 위의 1,2번 연산만으로 만들 수 있기 떄문에 index를 출력, 같지 않다면 -1을 출력한다. 

 

 

🥕 정답 코드 

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

index = 1
while  a<b:
    if b%2==0:
        b = b//2
    elif str(b)[-1]=='1':
        b = int(str(b)[:-1])
    else:
        break
    index +=1

if a==b:
    print(index)
else: print(-1)

위의 코드에서 수정하면 좋을 코드는 b = int(str(b)[:-1]) 를 ---> b = b//10 ! 다른 고수분들의 코드를 보고 배웠다.