문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B (1<= A < B <= 10^9)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다.
만들 수 없는 경우에는 -1을 출력한다.
겉보기에는 BFS의 전형적인 문제처럼 보이지만
이 문제는 다른 일반적인 BFS 문제와 한 가지 차이점이 있다.
입력값의 범위가 1 ~ 10^9로 매우 넓다는 점이다.
visited를 리스트로 선언할 경우, 0이 저장되어
쓸 데 없이 낭비되는 메모리가 너무 많아 비효율적인 코드가 된다.
그런데 이 문제는 graph가 주어지지 않기 때문에,
굳이 visited(graph)를 리스트로 선언할 필요가 없다.
따라서 이 문제의 경우 visited(graph)를 딕셔너리로 선언할 경우 더욱
효율적으로 동작하는 코드를 짤 수 있다.
메모리 초과 코드(visited 리스트 선언)
import sys
from collections import deque
a, b = map(int,sys.stdin.readline().split())
graph = [0 for _ in range(b+1)]
q = deque(); time = 1 # time 1 = 0초
graph[a] = time; q.appendleft(a)
while q:
x = q.pop(); time = graph[x] + 1
if x == b: break
for node in [(2*x),(10*x+1)]:
if node > b: continue
if graph[node] != 0: continue # 미방문 노드가 아닐 경우 continue
graph[node] = time; q.appendleft(node)
print(-1) if graph[b] == 0 else print(graph[b])
정답 코드 (visited 딕셔너리 선언)
import sys
from collections import deque
a, b = map(int,sys.stdin.readline().split())
graph = dict()
q = deque(); time = 1 # time 1 = 0초
graph[a] = time; q.appendleft(a)
while q:
x = q.pop(); time = graph[x] + 1
if x == b: break
for node in [(2*x),(10*x+1)]:
if node > b: continue
if node in graph: continue # 미방문 노드가 아닐 경우 continue
graph[node] = time; q.appendleft(node)
print(-1) if b not in graph else print(graph[b])