BAEKJOON_16953 "A -> B" PYTHON

[백준] 16953번 Python 파이썬

 

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

16953번: A → B

 

b에서 2를 나누거나 마지막 자리의 숫자 1을 빼서 a와 같게 만들어주도록 하였다.

처음에 작성한 코드는 시간 초과가 났다.

 

< 시간 초과 코드 >

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

while True:
    if a == b:
        print(result + 1)
        break
    elif b % 10 == 1:
        b = b //10
        result += 1          
        if b < a:
            print(-1)
            break
    elif b % 2 == 0:
        b = b // 2
        result += 1
        if b < a:
            print(-1)
            break

이전 코드는 b가 a보다 작은 경우가 while문 안에서 실행되었는데, while문 밖으로 빼주어 바로 -1을 출력하도록 하였다.

 

만약 b가 a보다 크다면, Greedy Algorithm을 이용하여 연산 횟수를 계산하도록 한다.

 

계산 중 2로 나누어 떨어지지 않으면서 마지막 자리의 수가 1이 아닌 경우 a와 같은 수로 만들 수 없기 때문에 '-1'을 출력하고 while문을 종료한다.

 

< 성공한 코드 >

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

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

if b == a:
    print(result + 1)
elif b < a:
    print(-1)

한 달 전에 틀리고 해결하지 못했는데 오늘 해결해서 너무 좋다 !!

혼자 공부하며 올리는 블로그입니다. 틀린 내용은 댓글 남겨주시면 감사하겠습니다.