16953 A->B

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

16953번: A → B

 

내가 풀었던 풀이(47%까지 맞았었는데 2줄 바꾸고 정답 맞춤)

a, b = map(int, input().split())
count = 0

while(b >= 1):
    if(b%2 != 0):
        b -= 1
        b = b / 10
        count += 1
        if(b == a):
            print(count + 1)
            break
    elif(b %2 == 0):
        b = b / 2
        count += 1
        if(b == a):
            print(count + 1)
            break
else:
    print(-1)

b가 b >= 1면 계속 수행한다.

b가 짝수가 아닌 경우: 처음엔 b = b//10으로 했지만 만약 b가 23인 경우엔 -1이 나와야하는데 그렇지 않다. 그래서 b -= 1, b = b / 10로 하니까 된다. 그래서 b==a가 되면 종료하고 출력한다.

b가 짝수인 경우: 계속 나누기 2를 한다.

 

deque를 이용한 풀이법

from collections import deque 

a, b = map(int, input().split()) 
res = -1 
que = deque([(a, 1)])#a가 2면, 덱에 2와 1이 있다.
while que:
    i, cnt = que.popleft() #왼쪽 값을 빼고싶으면 popleft()
    if i == b:
        res = cnt 
        break
    
    if i*2 <= b: #2로 곱하는 경우
        que.append((i*2, cnt+1))
    if int(str(i)+'1') <= b: #뒤에 1을 추가하는 경우
        que.append((int(str(i)+'1'), cnt+1)) 
print(res)

 

-2 162를 입력했을때 나오는 첫 결과

if문을 2개다 만족해서 2가지를 다 한 경우가 모두 deque에 들어간다.

 

-그 다음 while문

deque에 들어갔던 값을 돌리면 3가지의 경우가 나오게된다.

그러다가 i가 162가 된다면 종료를 한다.