백준 16953번
https://www.acmicpc.net/problem/16953

문제

후기

⏰ 풀이시간 20분 ++⏰

2를 곱하는 연산과, 1을 오른쪽에 추가하는 연산을 def()로 만들어서

모두 한번 씩 해보면 되지 않을까? 라는 어처구니 없는 알고리즘을 떠올렸고

구현 중 이건 절대 정답일 리 없다는 생각을 하고 처음으로 돌아왔다.

예제 입력 1에서

2->4->8->81->162 가 되는 것을 보고 거꾸로 생각해보니

162->81->8->4->2 이렇게 되는 것이었다.

어차피 앞에서 뒤로 연산하나 뒤에서 앞으로 연산하나 연산 횟수는 동일하기 때문이다.

갑자기 문제가 쉬워져 버렸다.

만약 2로 나누어 떨어지면 2로 나누고, 2로 나누어 떨어지지 않았을때

10으로 나눈 나머지가 1이면, 10으로 나눈 몫을 저장한다.

이 두가지 연산 모두 할 수 없다면, -1을 출력한다.

나의 풀이

import sys

input = sys.stdin.readline

A,B= map(int,input().split())
result = 1  #문제에서 최종 결과에서 1을 더하여 출력하라고 했으므로 

while B!=A: # 원하는 값이 될 때까지 연산한다.

    result +=1

    answer= B 

    if B%10 == 1: #21, 101 등 10으로 나눈 나머지가 1이면 

        B//=10  # 뒤에 1을 붙이는 연산을 할 수 있다는 뜻 

    elif B%2 ==0: #2로 나눈 나머지가 0이면 

        B//=2 #2로 나누는 연산을 할 수 있다는 뜻 

    if answer == B: #만약 위의 어떠한 연산도 할 수 없다면 

        print(-1) #-1 출력하고 종료 
        exit()

print(result)