728x90
https://www.acmicpc.net/problem/16953
16953번: A → B
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
www.acmicpc.net
2를 곱한 수와 10을 곱하고 1을 더한 수가 같을 수 없다는 점을 착안하고 목적수에 도달만 하면 무조건 리턴하게 하면 됩니다. 처음에는 dp 를 사용하려 했지만 메모리 초과때문에 저장하지 않고 비교만 해야합니다.
from collections import deque
def solution(A, B):
# 큐
queue = deque([[A, 1]])
# 계산
while True:
# 큐가 비면 끝
if not queue:
return -1
# 현재 수, 카운트
now_num, cnt = queue.popleft()
# 목적수에 도달하면 리턴
if now_num == B:
return cnt
# 메모 비교 및 최신화
# x2
if now_num*2 <= B:
# 큐에 추가
queue.append([now_num*2, cnt + 1])
# x10 + 1
if now_num*10 + 1 <= B:
# 큐에 추가
queue.append([now_num*10 + 1, cnt + 1])
A, B = map(int, input().split())
print(solution(A, B))
728x90
'Coding Test > BaekJoon_Python' 카테고리의 다른 글
백준 14502 <연구소> Python (2) | 2023.11.20 |
---|---|
백준 11399 <ATM> Python (1) | 2023.11.19 |
백준 1764 <듣보잡> Python (0) | 2023.11.16 |
백준 1389 <케빈 베이컨의 6단계 법칙> Python (1) | 2023.11.16 |
백준 1007 <벡터 매칭> Python (1) | 2023.11.15 |