[백준 16953번] A -> B

http://www.acmicpc.net/problem/16953

16953번: A → B

 

 

# 조건

• 정수 A를 B로 바꾸려고하는데 가능한 연산은 아래 두 가지이다.
  • 2를 곱한다.
  • 1을 수의 가장 오른쪽에 추가한다.
• A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

 

# 접근 방법

• 만들 수 없는 경우에는 -1을 출력한다.
• B+1만큼의 빈 리스트를 만들어서 BFS 탐색해준다.
• A에서 2를 곱한 수와 1을 오른쪽에 추가한 수에 현재 카운트를 기록해주며
  • B를 만난 경우 종료 해준다.

 

 

 

 

메모리 초과

모든 숫자에 대해 리스트에 기록해주니 입력이 커서 메모리초과

import sys  
sys.stdin = open('input.txt')  
from collections import deque  
input = sys.stdin.readline  
  
  
a, b = map(int, input().split())  
  
bfs = [-1] * (b+1)  
  
bfs[a] = 1  
  
q = deque()  
q.append(a)  
while q:  
    num = q.popleft()  
    now_num = num*2  
    if now_num <= b and bfs[now_num] < 0 :  
        q.append(now_num)  
        bfs[now_num] = bfs[num] + 1  
  
    c = str(num) + str(1)  
    new_num = int(c)  
    if new_num <= b and bfs[new_num] < 0 :  
        q.append(new_num)  
        bfs[new_num] = bfs[num] + 1  
  
  
print(bfs[b])

 

 

 

 

pass 코드

• 따라서 deque에 카운트 값을 넣어주는 걸로 대체
• b를 만들 수 있다면 flag = True 로 변경해주어 cnt 출력
• 아니라면 -1 출력

import sys  
sys.stdin = open('input.txt')  
from collections import deque  
input = sys.stdin.readline  
  
  
a, b = map(int, input().split())  
q = deque()  
q.append((a,1))  
flag = False  
while q:  
    num,cnt = q.popleft()  
    now_num = num*2  
    if num == b:  
        flag = True  
        break    if now_num <= b:  
        q.append((now_num,cnt+1))  
  
    c = str(num) + str(1)  
    new_num = int(c)  
    if new_num <= b:  
        q.append((new_num,cnt+1))  
  
if flag:  
    print(cnt)  
else:  
    print(-1)