[BaekJoon] "그리디" - 백준 16953번 문제 : A -> B

[문제 설명]

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

16953번: A → B

 

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

1. 2를 곱함

2. 1을 수의 가장 오른쪽에 추가함

A를 B로 바꾸는데 필요한 연산의 최솟값 구함

 

출력: 연산의 최솟값 +1, 만들 수 없는 경우에 -1 출력

 

[해결 로직]

- 거꾸로 연산을 하면됨

- 곱하기 2는 나누기 2로, 1을 오른쪽에 추가하는건 반대로 1을 빼서 10으로 나눈 몫임

- 10으로 나누는게 더 크기 때문에, 10으로 나눴을 때의 나머지가 1인 경우 먼저 확인

- 그 다음에 2로 나눠떨어지는지 확인

- 이러한 연산을 반복하면서 연산 횟수 카운팅

- 모든 연산이 다 끝난 후에 숫자가 입력된 N과 같은 경우에는 cnt +1 출력, 그렇지 않으면 -1 출력

 

[Solution 코드]

n,m = map(int, input().split())

## 곱하기 2는 나누기 2로
## 1을 오른쪽에 추가하는건 반대로 1을 빼서 10으로 나눈 몫임

cnt = 0

while m != n and m > 0:



    if (m % 10) == 1: ## 이 조건을 해줘야함 단순이 홀짝인지만 확인하면 안됨
        m = int((m-1)//10)
        cnt += 1

    elif m % 2 == 0: ## 먼저 2로 나눠 떨어지는지 확인
        m = int(m // 2)
        cnt += 1

    else:
        cnt = -1
        break
if m != n:
    print(-1)
else:
    print(cnt + 1)