[파이썬] 16953. A -> B

문제

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

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

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

입력

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

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에

1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

예제 입력 1 

2 162

예제 출력 1 

5

2 → 4 → 8 → 81 → 162

예제 입력 2 

4 42

예제 출력 2 

-1

예제 입력 3 

100 40021

예제 출력 3 

5

100 → 200 → 2001 → 4002 → 40021

 

 

👱‍♀️ 나의 풀이

 

여러번 시도 끝에 ㅠㅠㅠㅠㅠ

 

import sys

input=sys.stdin.readline
A, B=map(int, input().split())
ans=1

while A < B :
    if B % 10 == 1 :    # 뒤에 1 제거
        B=int(str(B)[:-1])
        ans+=1
        continue
    if B % 2 == 0 :
        B//=2
        ans+=1
    else :
        break

if A == B :
    print(ans)
else :
    print(-1)

 

B에서 A를 만들기 위해 2로 나누거나 1을 제거한다.

첨에는 아래 소스 코드처럼  A < B만 고려했는데 B가 2로 나누어 떨어지지 않아도 그냥 2로 나누고 있는 것을 알았다.

 

# 실패
import sys

input=sys.stdin.readline
A, B=map(int, input().split())
ans=1

while A < B :
    if B % 10 == 1 :    # 뒤에 1 제거
        B=int(str(B)[:-1])
        ans+=1
        continue
    B//=2
    ans+=1

if A == B :
    print(ans)
else :
    print(-1)

 

B에서 A를 만들었다.

일의 자리가 1이면 1을 제거했다.

그렇지 않으면 B를 2로 나누었다.

A가 B보다 작을 동안 이 과정을 반복했다.

만약 A=1, B=5라면 -1이 나와야하지만 3이 나오므로 잘못된 코드

B가 2로 나누어 떨어지지 않거나 일의 자리수가 1이 아닌 경우도 포함해야한다.

 

# 메모리 초과
import sys

input = sys.stdin.readline
A, B = map(int, input().split())
ans=1
flag=False

def cal(dp) :
    global ans, flag
    ans+=1
    temp = list()
    for x in dp :
        num1=x * 2
        num2=int(str(x) + "1")
        temp.append(num1)
        temp.append(num2)
        if num1 == B or num2 == B :     # 성공
            flag=True
            return
    if min(temp) > B :    # 실패
        return

    cal(list(set(temp)))

cal([A])
if flag :
    print(ans)
else :
    print(-1)

 

재귀로 구현했다.

모든 경우의 수를 구하고 set으로 중복을 제거한 후 다시 리스트로 만들어 함수에 입력으로 넣었다.

메모리 초과 ㅠㅠ

 

 

🧑 다른 사람 풀이

 

# https://alpyrithm.tistory.com/118
from collections import deque

a, b=map(int, input().split())
res=-1
que=deque([(a, 1)])
while que :
    i, cnt=que.popleft()
    if i == b :
        res=cnt
        break

    if i*2 <= b :
        que.append((i*2, cnt+1))
    if int(str(i)+'1') <= b :
        que.append((int(str(i)+'1'), cnt+1))

print(res)

 

bfs로 구현

2를 곱하거나 1을 오른쪽에 추가한 수가 b보다 같거나 작아야 que에 추가된다.

 

# https://alpyrithm.tistory.com/118
a, b=map(int, input().split())
cnt=1
while True :
    if b == a :
        break
    elif (b % 2 != 0 and b % 10 != 1) or b < a :
        cnt=-1
        break
    else :
        if b % 10 == 1 :    # 끝자리가 1이면 1 떼기
            b//=10
            cnt+=1
        else :
            b //= 2
            cnt+=1

print(cnt)

 

b에서 a로 만들기 위해 1을 떼거나 2로 나눈다.

1. b랑 a가 같거나

2. b를 2로 나눌 수 없고 일의 자리가 1이 아니거나 b가 a보다 작다

위 두 가지 경우 중 하나에 속하면 반복문을 빠져나온다.

b//=10을 하면 일의 자리수를 제외시킬 수 있었는데 난 슬라이싱을 했네,,,🙄

 

 

n, m=map(int, input().split())
count=0
while n != m :
    if n > m :
        count=-2
        break
    elif str(m)[-1]=='1' :
        m=m//10
        count+=1
    elif m % 2 ==0 :
        m=m//2
        count+=1
    else :
        count=-2
        break
print(count+1)

 

m을 n으로 만드는 연산을 한다.

n과 m이 같지 않을 동안 반복한다.

n이 m보다 커지거나 m이 홀수면서 일의 자리가 1이 아니면 break한다.

 

 

문제 출처 👉 백준