A -> B

백준 16953

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

• 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
  • 2를 곱한다.
  • 1을 수의 가장 오른쪽에 추가한다.
• 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
• A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

입출력

입력	출력
2 162	5
4 42	-1
100	40021

---

접근 방식

: bfs로 가능한 두가지 연산에 대해 탐색하였다.

알게된 점

• 처음에 bfs로 풀 때 visited배열을 b의 크기만큼 0으로 초기화해서 연산 횟수를 저장했는데, 10^9까지 수가 주어져 메모리 초과가 난다. --> q에 숫자와 횟수를 함께 append해서 횟수를 달고 다녀야 한다.
• 그리디로 문제를 풀 수도 있다.

코드

bfs 방식

from collections import deque
import sys

def bfs(a, b, visited):
    q = deque()
    q.append((a,1))
    visited.append((a,1))

    while q:
        x, cnt = q.popleft()
        if x == b:
            return cnt

        # 2를 곱한다
        if 2*x<=b and 2*x not in visited:
            new = cnt + 1
            q.append((2*x, new))

        # 1을 추가한다
        if int(str(x)+'1')<=b and int(str(x)+'1') not in visited:
            new = cnt + 1
            q.append((int(str(x)+'1'), new))

    return -1

a, b = map(int, sys.stdin.readline().split())
visited = []
print(bfs(a, b, visited))

그리디 방식

import sys
a, b = map(int, sys.stdin.readline().split())

cnt = 1
while True:
    if b==a:
        print(cnt)
        break

    elif a>b or (b%10!=1 and b%2!=0):
        print(-1)
        break

    elif b%10 == 1:
        b //= 10
        cnt += 1
        
    elif b%2 == 0:
        b /= 2
        cnt += 1