[백준] 16953 A → B

문제

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

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

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

입력

첫째 줄에 $A, B$ ( $1 ≤ A < B ≤ 10^9$ )가 주어진다.

출력

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

내 풀이

from collections import deque

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

q = deque()
q.append((b, 0))

visited = set()
visited.add(b)

found = False
while q:
    s, cnt = q.popleft()
    if s == a:
        print(cnt+1)
        found = True
        break
    
    if s%2 == 0:
        if 0 <= s/2 < b+1 and int(s/2) not in visited:
            visited.add(int(s/2))
            q.append((int(s/2), cnt+1))
            
    if (s-1)%10 == 0:
        if 0 <= (s-1)/10 < b+1 and int((s-1)%10) not in visited:
            visited.add(int((s-1)/10))
            q.append((int((s-1)/10), cnt+1))
            
if not found:
    print(-1)

시간 복잡도 → $O(N)$
BFS의 시간 복잡도를 지님 ( $N$ 은 최대 $10^9$ )
공간 복잡도 → $O(N)$
visited와 deque에 최대 $N$ 개까지 저장될 수 있음

코멘트

처음에는 백준 1697 숨바꼭질 문제와 비슷하다고 생각하여 같은 접근법으로 풀었는데 메모리 초과가 떴다. 분명 숨바꼭질 문제의 메모리 제한이 128 MB이고 이 문제는 256 MB로 두 배인데 왜 그런가 해서 봤더니 숨바꼭질은 숫자가 최대 $10^5$ 이고 이 문제는 $10^9$ 까지 커져서 그런 것이었다. 그래서 visited 배열을 그대로 사용하면 최대 $10^9$ 개의 -1을 저장하게 되어서 메모리 초과가 발생한다.

그래서 이 문제에서는 1) a → b가 아니라 b → a로 접근하고, 2) visited 배열을 리스트가 아닌 set 사용, 3) 그에 따라 count는 queue에 같이 넣었다 빼면서 1씩 증가시키기 의 방법을 사용했다.

a → b가 될 수 없는 경우는 BFS 탐색을 끝내고도 아무런 출력이 없는 상태이므로 found라는 변수를 선언하여 while 문 내에서 if s == a: found = True를 해준 뒤 마지막에 if not found: print(-1) 을 하면 된다.

⚠ A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력해야 한다는 것에 유의하자.

[백준] 16953 A → B

문제

입력

출력

내 풀이

코멘트

References