[백준 - Python] 16953. A → B (그리디)

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

16953번: A → B

 

코드

# 2로 나눠지면 나누기
# 일의 자리 수가 1이면 1 제거하기

a, b = map(int, input().split())
cnt = 0
while b > 0:
    if b % 2 == 0:
        b //= 2
        cnt += 1
    elif b % 10 == 1:
        b //= 10
        cnt += 1
    else:
        if a == b:
            cnt += 1
            break
        cnt = -1
        break
    if a == b:  # 추가
        cnt += 1
        break
    if b <= 0:
        cnt = -1

print(cnt)

 

문제는 A를 B로 바꾸는데 필요한 최소 연산 횟수이지만,

A→B 방향으로는 최소 연산 횟수를 구하기는 어렵겠다고 판단했다.

 

연산의 특징을 보았을 때,

B에서 역으로 연산을 확인하면서 만족하는 A가 존재하는지 확인하는 방식으로 문제를 해결했다.