[Python] A→B (백준 16953번 파이썬)

문제

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

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

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

입력

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

출력

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

예제 입력 1

2 162

예제 출력 1

5

2 → 4 → 8 → 81 → 162

예제 입력 2

4 42

예제 출력 2

-1

예제 입력 3

100 40021

예제 출력 3

5

100 → 200 → 2001 → 4002 → 40021

 

문제 이해

- 프로그래머스의 점프와 순간이동 문제와 비슷하지만 더 간단한 문제였습니다. 문제를 뒤에서부터 접근(Bottom-Up)하는 방식이 동일하기 때문에 그렇게 느낀 것 같습니다.

- 그리디 알고리즘으로 해결할 경우 a-> b 순이 아닌, b->a 순으로 생각하면 문제가 간단해집니다.

- 제한조건에서 a와 b에 대한 조건이 정해져있으므로 이 조건과 일치하지 않으면 반복문을 종료합니다.

- 문제를 뒤에서 부터 생각해 b를 a로 만드려고 할 때, 2로 나누는 것보다 1을 제거하는 것이 연산의 횟수를 더 줄일 수 있습니다.(단순 나누기와 자릿수 제거)

- 따라서 b가 1의 자리가 1인 수라면 1을 제거합니다. (10으로 나눈 몫, 나머지 이용)

- 1의자리가 1인 수가 아닌, 짝수라면 2로 나눕니다.

- 위의 둘에 해당하지 않는다면, 문제의 조건을 벗어나므로 종료합니다.

 

코드

#백준 16953 A -> B

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

count = 1

while True:

    if a == b:

        break

    if a > b:

        count = -1

        break

   

    if b%10 == 1:

        b = b//10

        count += 1

    elif b%2 == 0:

        b = b//2

        count += 1

    else:

        count = -1

        break

print(count)

 

해당 문제는 BFS알고리즘으로도 해결할 수 있다고 합니다. 내일은 BFS로 해결해보겠습니다.