[Baekjoon]백준 16953 A → B(실버 2) - Python

문제설명

문제를 살펴보면 A 정수를 B로 만드는데, 2를 곱하거나 숫자의 끝자리에 1을 추가하는 방식으로만 이루어진다

만약, 해당 방법으로는 B로 만들수 없다면 -1을 출력하는 문제이다

우선적으로, A에서 B를 만드는 방법도 고려해보았으나 최솟값을 구해야한다는 점, 그리고 B를 정확하게 맞추어야하기 때문에

코드상에서는 B에서 A를 만드는 방법이 더욱 간단할 것이라 생각하였다

 

그래서 while문을 통해 두번째로 입력받은 숫자가 첫번째로 입력받은 숫자보다 같거나 작아질때까지

연산을 반복적으로 수행하도록 작성하였다 연산을 반복할 때 끝자리가 1인 경우는 이전에 1을 붙인 경우밖에

없기 때문에(2를 곱해서 1이 나올수 없기 때문) 끝자리가 1이라면 10을 나누어 숫자를 복구해준다

만약 그게 아니라면 무조건 2를 곱한 것이기 때문에 2로 나누어 준 후 cnt 변수에 1을 더해주는 방식으로 작성하였다

마지막에는 첫번째 숫자와 두번째 숫자가 같다면 정상적으로 B -> A가 수행된 것이기 때문에 cnt + 1을 출력해주고

아니라면 -1을 출력하도록 작성해주었다

import sys
input = sys.stdin.readline

first_num, second_num = map(int, input().split())
cnt = 0
while first_num < second_num:
    if second_num % 10 == 1:
        second_num //= 10
        cnt += 1
        #print(second_num)
    else:
        second_num //= 2
        cnt += 1
        #print(second_num)
        
if first_num == second_num:
    print(cnt+1)
else:
    print(-1)

하지만 코드를 제출해보았더니 틀렸습니다를 만났다 주어진 예제와 질문게시판에서 발견한 반례를 넣어보아도

정답으로 출력되길래 계속해서 찾아보았는데 3 100 의 경우 오류가 발생하였다 -1이 출력되어야하지만 6이 정답으로 출력된다

100 - 50 - 25 - 12 - 6 - 3의 과정을 거치게되는데, // 연산자에 의해 25에서 1이 나머지로 남지만 버려지기 때문에

해당 부분에서 문제가 발생한다 따라서 2로 나누었을때 나머지가 0인지 확인하는 로직이 추가적으로 필요하다

import sys
input = sys.stdin.readline

first_num, second_num = map(int, input().split())
cnt = 0
while first_num < second_num:
    if second_num % 10 == 1:
        second_num //= 10
        cnt += 1
        #print(second_num)
    elif second_num % 2 == 0:
        second_num //= 2
        cnt += 1
        #print(second_num)
    else:
        break

if first_num == second_num:
    print(cnt+1)
else:
    print(-1)

만약 2로 나누어지지 않는다면 이는 만들수없는 숫자라는 뜻이 되기 때문에 break를 해주면 된다