백준 16953 - A → B ( Python )

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

16953번: A → B

그리디 알고리즘의 일종이라고도 볼 수 있는 것 같다

 

풀이

1. b가 짝수인 경우 2로 나눌 수 있음

2. 1로 끝나는 경우 1제거
3. 짝수이면서 1로 끝나는 경우는 없으므로 if ~ elif로 작성

 

풀이 방식을 떠올리는 건 어렵지 않았다.

하지만 1로 끝나는 경우 1제거하는 방식을 문자열로 치환후 slice하였는데

다른 사람 풀이를 확인해보니 10으로 나눈 나머지로 분기를 정할 수 있었다..

문제의 전제가 숫자였으니 이런 방식도 떠올려야하는데 아직 알고리즘 풀이가 많이 부족하다ㅠ

힘내자...

 

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

# 최솟값에 1을 더한 수를 출력해야하므로 1부터 시작
count = 1

# a가 b보다 작을 때 까지 반복하면된다.
while a < b:

	# 짝수인 경우 2로 나누기
    if b % 2 == 0:
        b //= 2
        
    # 10으로 나눈 나머지는 일의 자리수만 남게 된다 -> 1을 빼는 것음 10으로 나눠주면됨     
    elif b % 10 == 1:
        b //= 10
    else:
        break
    # 루프 한 번을 돌 때 계산을 한 번 진행하게되므로 count +=1
    count += 1
    
if a == b:
    print(count)
else:
    print(-1)