파이썬 알고리즘 160번 | [백준 16953번] A -> B - 진행 중

160. A -> B

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>

참고 풀이 : https://codesyun.tistory.com/294

1)

import sys
a,b=map(int, sys.stdin.readline().rstrip().split())
# 2 곱하기, 1을 수의 가장 오른쪽 추가
# a-> b 연산의 최솟값에 1을 더한 값 출력, 만들 수 없음 -1
cnt=0

while a!=b:

    if b%2==0:
        b//=2
        cnt+=1
    elif str(b)[-1] == '1' :
        b//=10
        cnt+=1
    elif a>b:
        cnt=-2
        break
    else :
        cnt=-2
        break
    print(cnt+1)
    

2) 혹은 BFS로 풀 수도 있다고 한다!

a,b  = map(int,input().split())
ans = 1e9

def dfs(a,cnt):
    global ans
    if a == b:
        ans = min(ans,cnt)
        return
    if a > b:
        return
    dfs(a*2,cnt+1)
    dfs(int(str(a)+"1"),cnt+1)

dfs(a,1)
if ans != 1e9:
    print(ans)
else:
    print(-1)

<내 틀렸던 풀이, 문제점>

import sys
a,b=map(int, sys.stdin.readline().rstrip().split())
# 2 곱하기, 1을 수의 가장 오른쪽 추가
# a-> b 연산의 최솟값에 1을 더한 값 출력, 만들 수 없음 -1
cnt=0

while a!=b:

    if b%2==0:
        b//=2
        cnt+=1
    elif str(b)[-1] == '1' :
        b//=10
        cnt+=1
    elif a>b:
        cnt=-2
        break
    else :
        cnt=-2
        break
    print(cnt+1)
    

<반성 점>

• 앞에서 -> 뒤로 나아가는 사고보다
• 뒤를 줄여서 앞으로 나아가는 사고도 해보자!

<배운 점>