[백준알고리즘/16953번/파이썬] A -> B

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

16953번: A → B

문제: A, B가 주어졌을 때, 2를 곱하거나 수의 가장 오른쪽에 1을 붙이는 연산을 통해 A를 B로 바꾸는데 필요한 연산 횟수를 출력하는 문제

 

풀이 방법: top- down , bfs

 

1번 풀이 코드:

 

<top-down>

import sys

a,b = map(int,sys.stdin.readline().rstrip().split())
cnt = 0
pause = 0

while b != a and b >= a:
    cnt += 1
    if b % 10 == 1:
        b //= 10
    elif b % 2 == 0:
        b //= 2
    else:
        pause = 1
        break

if not pause and a==b:
    print(cnt+1)
else:
    print(-1)

 

풀이 설명:

결과 값이 주어지므로, top - down 방식으로 구현하는 방법으로 코드를 짜보았습니다.

수의 오른쪽에 1을 붙이는 연산은 반대로 수를 10으로 나눴을 때 나머지가 1이라는 뜻입니다.

*2의 연산은 반대로 나누기 2 입니다.

 

따라서 다음과 같이 구현하였습니다.

while문의 종료조건은 b(나눠지는 수)가 a 같거나 크면서 같지 않을 때 연산이 진행되도록 하였습니다.

 

if b % 10 == 1:
    b //= 10
elif b % 2 == 0:
    b //= 2
else:
    pause = 1
    break

if문과 elif 문의 조건에 부합하지 못하는 경우는 구할 수 없는 수 이므로, pause 값을 1로 설정해주고 반복문을 종료해줍니다.

 

if not pause and a==b:
    print(cnt+1)
else:
    print(-1)

pause에 아무런 값이 설정되지 않고 a 가 b와 동일할 경우, 연산 횟수를 출력해줍니다.

 

 

2번 풀이코드: bottom-up 방식으로 bfs 입니다.

 

import sys
from collections import deque

a, b = map(int,sys.stdin.readline().rstrip().split())
deq = deque([(a,1)])
tot = -1

while len(deq) > 0:
    val, cnt = deq.popleft()
    if 2 * val <= b:
        deq.append([2*val,cnt + 1])

    if val*10+1 <= b:
        deq.append([10*val + 1 , cnt+1])

    if 2*val == b or 10*val + 1 == b:
        tot = cnt + 1
print(tot)

풀이 설명:

주어진 a 부터 b를 구해 나가는 과정입니다.

 

if 2 * val <= b:
    deq.append([2*val,cnt + 1])

if val*10+1 <= b:
    deq.append([10*val + 1 , cnt+1])

 

위와 같이, 두가지 연산에 대하여 조건을 충족할 경우 deque에 값을 추가해줍니다.

 

if 2*val == b or 10*val + 1 == b:
    tot = cnt + 1

연산을 하다보면, 원하는 값에 도달하는 경우가 있는데 이 경우 변수에 count 값을 저장하도록 하였고

만약 값에 도달하지 못하거나 값을 넘어가게 되면 while문의 종료조건을 통해 종료 되도록 설정하였습니다.

 

1번 top-down

2번 bottom-up

속도는 top-down 방식이 약 2배 빠른 것으로 나왔습니다. 아마 단순 연산이기 때문에 deque를 거치는 것이 오히려 더 느린 것이 아닐까 생각합니다.