[백준] 16953 - A -> B

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

16953번: A → B

문제 한줄 이해

-A숫자를 2배, A숫자 뒤에 1 붙이기를 해가면서 B가 되기위한 최소 횟수 구하기

 

생각난 풀이

1번째 방법: 숫자의 연산을 해주고 탐색을 진행하는 BFS 아이디어를 떠올려 적용해봤다. 

이유는       A

           2*A   A1    이런식으로 계속 숫자들이 뻗어 나가기 때문이다.

import sys
from collections import deque
#숫자에 1을 붙여주기위해 문자연산이 가능하게 str로
a, b = map(str,sys.stdin.readline().split())

que = deque()
#큐에 횟수와 현재숫자를 담기
que.append((1,a))
result = 0
while que:
    cnt, nownum = que.popleft()
    if nownum == b:
        result = cnt
        break
    #*2연산과 1을 끝에 붙여주는 연산
    for i in (str((int(nownum)*2)),(nownum+"1")):
    # 이미 i가 b보다 크다는건 더이상 탐색할 필요가 없다.
        if int(i) <= int(b):
            que.append((cnt+1,i))
if result == 0:
    print(-1)
else:
    print(result)

정답 처리는 됐지만 형변환 할때에 시간이 꽤나 걸리는걸로 알고있어서 타입을 맞춰줄 생각을 해봤다.

 

2번째 방법: 무작정 문제를 풀려고 들다보니 아주 간단한 방법을 잊고있었다. 숫자에 *10을 해주고 +1을 해주면 되는데 말이다!

import sys
from collections import deque
a, b = map(int,sys.stdin.readline().split())

que = deque()
que.append((1,a))
result = 0
while que:
    cnt, nownum = que.popleft()
    if nownum == b:
        result = cnt
        break
    for i in ((nownum)*2),(nownum*10+1):
        if i <= b:
            que.append((cnt+1,i))
if result == 0:
    print(-1)
else:
    print(result)