[Python] 백준 16953번 - A -> B

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

16953번: A → B

 

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 그래프 이론
 - 그리디 알고리즘
 - 그래프 탐색
 - 너비 우선 탐색

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

 

---

보자마자 DP로 풀어야 하나..? 싶었다.

근데 DP로 풀면 풀 수 없는 문제이다. 각 경우의 수가 2가지씩 계속해서 늘어나기 때문에 풀 수 없었다.

 

그래서 고민하다가 BFS와 Queue를 이용해서 풀 수 있을 것 같은데 도저히 방법이 떠오르지 않았다.

 

https://my-coding-notes.tistory.com/210

[🥈1 / 백준 16953 / 파이썬] A → B

 

해당 블로그로부터 소스를 얻어서 풀 수있었다.

 

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

q = deque()
q.append((a, 1))
flag = False
while(q):
    n, cnt = q.popleft()
    if n > b:
        continue
    if n == b:
        print(cnt)
        flag = True
        break
    q.append( (int(str(n)+"1"), cnt+1))
    q.append((n*2, cnt+1))
if flag == False:
    print(-1)

큐에 1을 붙인 것과, 2를 곱한 것을 넣고 반복문을 돌 때마다 pop 하여 값을 확인한다.

 

값을 다 확인할 때까지 cnt가 출력되지 않으면 -1 출력

 

DP와 유사하지만 다른 점은 계속해서 pop을 하면서 공간의 사용량을 줄여준다는 점이었다.

 

위 방식은 A에서 B로 갔으니 Bottom-Up이라고 한다면

 

Top-Down 형식으로 B에서 A로 가는 방법도 있다.

 

import sys
from collections import deque
input = sys.stdin.readline
a, b = map(int, input().split())
cnt = 1
while b != a:
    cnt += 1
    tmp = b
    if b % 10 == 1:
        b //= 10
    elif b % 2 == 0:
        b //= 2
    if tmp == b:
        print(-1)
        break
else:
    print(cnt)

1의 자릿수가 1이면 맨 뒤 1을 빼주는 게 가장 빠른 방법일태고

 

그다음 2로 나누어진다면 2로 나누는 것이 베스트

 

tmp에 기존의 b 값을 저장하여 아무 변화가 없다면 더 이상 진행방법이 없다는 뜻으로 -1 출력

 

b == a 조건이 발동했더라면 하단의 else에서 cnt값이 출력될 것이다.