Python - A -> B (16953) 그리디, 재귀

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

16953번: A → B

1. 재귀

 - 이진 트리 모양으로 뻗어 나가면서 모든 경우를 해보는 방법

 

2. 그리디

 - 만들어야 하는 수를 원래 수로 만드는 방향

 - 1순위 : 10으로 나누었을 때 1이 남으면 10으로 나눔

 - 2순위 : 2로 나누어 떨어지면 2로 나눔

 - 나누어 떨어지지 않거나 원래 수보다 작아지면 답은 -1

 

재귀 코드

import sys
input = sys.stdin.readline
n, m = map(int, input().strip().split())
ans = -2
def pro(x, y, d):
    global ans
    if ans != -2 or x > y: return
    if x == y:
        ans = d
        return
    pro(x * 2, y, d + 1)
    pro(x * 10 + 1, y, d + 1)
pro(n, m, 0)
print(ans + 1)

 

 

그리디 ( 재귀보다 30ms 정도 더 빠름)

import sys
input = sys.stdin.readline
n, m = map(int, input().strip().split())
ans = 0
while 1:
    if m < n:
        ans = -2
        break
    if n == m:
        break

    if m % 10 == 1:
        m //= 10
    elif m % 2 == 0:
        m //= 2
    else:
        ans = -2
        break
    ans += 1
print(ans + 1)