[16953] A -> B

초안

메모리 초과가 난 코드

10억개의 메모리를 생성하려고해서 메모리 초과가 났다

 BFS로 만들었었다.

import sys
from collections import deque

input = sys.stdin.readline

A, B = map(int, input().strip().split())

num = [sys.maxsize for _ in range(B + 1)]

answer = -1

q = deque([A])
num[A] = 1
while q:
    cur = q.popleft()
    # 정답인지 검사
    if cur == B:
        answer = num[cur]
        break
    # *2를 했을 때 b보다 안커지는지 검사
    elif cur > B:
        q.popleft()
        continue
    nxt = cur * 2
    if nxt > B:
        continue
    else:
        num[nxt] = min(num[nxt], num[cur] + 1)
        q.append(nxt)
    # +1을 했을 때 b보다 안커지는지 검사
    nxt = int(str(cur) + "1")
    if nxt > B:
        continue
    else:
        num[nxt] = min(num[nxt], num[cur] + 1)
        q.append(nxt)

print(answer)

 

큐에 횟수를 넣으라는 재미나이의 힌트를 받아 수정해서 제출했더니 맞았다.

추가로 다른 아이디어로 그리디방식으로 B -> A로 하면 더 편하다는 제안도 받았었지만 이미 BFS로 다 만들어 놨기 때문에 그냥 이렇게 만들었다.

import sys
from collections import deque

input = sys.stdin.readline

A, B = map(int, input().strip().split())

answer = -1

q = deque([(A, 1)])
while q:
    cur, cnt = q.popleft()
    # 정답인지 검사
    if cur == B:
        answer = cnt
        break
    # *2를 했을 때 b보다 안커지는지 검사
    elif cur > B:
        q.popleft()
        continue
    nxt = cur * 2
    if nxt > B:
        continue
    else:
        q.append((nxt, cnt + 1))
    # +1을 했을 때 b보다 안커지는지 검사
    nxt = int(str(cur) + "1")
    if nxt > B:
        continue
    else:
        q.append((nxt, cnt + 1))

print(answer)