[BOJ] [Python] 16953번 : A → B

처음 설계

 

#시간 초과

num = input().split()

a = int(num[0])
b = int(num[1])

def find_b(a, b):
    count = 1
    while(b != a): # A와 일치하는가?
        check_box = [b]
        if(b % 2 == 0): # 2로 나누어지는가?
            go_while = 0
            while(check_box[len(check_box)-1] % 2 == 0):
                print(check_box)
                check_box.append(check_box[len(check_box)-1] // 2)
                for ready_num_b in range(len(check_box)):
                    if(check_box[ready_num_b] < a): # A보다 작은가?
                        if(ready_num_b-1 != -1): #그 전의 수로 돌아갈 수 있다?
                           count += len(check_box)-1
                           b = check_box[ready_num_b-1]
                           check_box = [b]
                           go_while = 1
                           break

                        else:
                            return -1
                    if(ready_num_b == len(check_box)-1):
                        b = check_box[ready_num_b]
                if(go_while == 1):
                    break

        elif(str(b)[len(str(b))-1] == '1'): # 1이 제거 되는가?
            count += 1
            b = int(str(b)[:len(str(b))-1])
            if(b != a): # A와 일치하는가?
                if(b < a): # A보다 작은가?
                    return -1
            else:
                return count
        else:
            return -1
    return count

print(find_b(a, b))

 

시간 초과가 발생했다.

이 설계의 문제점을 해결하기 위해서

1. 중복되는 부분 제거

2. 불필요한 연산 제거

를 하였다.

 

 

최종 설계

 

num = input().split()

a = int(num[0])
b = int(num[1])

count = 1

while(True):
    if(b == a):
        break
    elif(b % 2 != 0 and int(str(b)[len(str(b))-1]) != 1 or (b < a)):
        count = -1
        break
    else:
        if(b % 2 == 0):
            b = b // 2
            count +=1
        else:
            b = int(str(b)[:len(str(b))-1])
            count += 1

print(count)