[Python] 백준 풀기 16953 - A → B

파이썬 백준 16953번

실버2

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

16953번: A → B

 

 

 

 

 

문제 보기

분류: 그리디 알고리즘, 그래프 탐색, 너비 우선 탐색

 

 

 

 

 

문제 풀기

A 에서 B 로 가지 않고 B 에서 A 로 가능한지를 바라보았다.

 

 

while 을 통해 B 가 짝수일 때는 2 로 나누고, 맨 뒷자리 1 이 있을 때 1 을 제거하여 답을 찾을 때까지 반복한다.

함수 fnConversion() 에 적용된 조건은 다음과 같다.

1. 제일 먼저 B 와 A 가 같은지 비교하여 결과를 내보내고 while 을 멈출 수 있도록 한다.

2. 변환이 불가능한 경우에 대한 조건으로 B 가 A 보다 작아지는 시점을 찾거나 맨 뒷자리 숫자가 1 이 아닌 홀수가 나올 때 while 을 멈춘다.

3. B 가 짝수일 때 2 로 나눈다.

4. B 의 맨 뒷자리 숫자가 1 일 때 10 으로 나눈 몫을 구해 1 의 자리를 없앤다.

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline


def fnConversion(A, B):
    count = 0
    while True:
        count += 1
        if B == A:
            print(count)
            break
        elif B < A or (B % 2 == 1 and B % 10 != 1):
            print(-1)
            break
        elif B % 2 == 0:
            B = B / 2
        elif B % 10 == 1:
            B = B // 10


if __name__ == "__main__":
    A, B = map(int, inputdata().split())
    
    fnConversion(A, B)