16953번 A -> B

이 문제는 그리디 알고리즘을 이용해 풀었다.

 

문제풀이

정수 A를 B로 변환하는 문제이다.

처음에는 A를 증가 시키면서 변환하는 코드를 짰지만 B를 감소 시키면서 A를 찾아가는 것이 좀 더 이해하기 쉬운 코드로 짤 수 있었다.

 

1. A와 B의 값을 비교하여 A가 더 크지 않은지 그리고 연산 가능한 조건들을 충족 하는지를 확인한다. 충족하지 않는다면 -1의 값을 출력한다.

2. B를 2로 나누었을 경우 나머지가 0이었을때, 나누어진 몫을 저장한다. 1번째 조건에 따른다.

3. B를 10으로 나누었을 경우 나머지가 1이었을 때, 1을 제거해주고  몫을 저장한다. 2번째 조건에 따른다.

4. 그리고 A와 B의 값이 같을때 반복을 중단하고 최종 값을 출력한다.

 

이때 한가지 조심해야 할 것이 있는데 처음부터 A와 B의 값이 같을 경우를 생각해서 count의 초기 값을 1로 설정하고 진행해야 맞을 수 있다.

 

코드

 

import sys

A, B = map(int, sys.stdin.readline().split())
count = 1
while True:
    if A == B: break
    elif A > B or (B % 10 != 1 and B % 2 != 0):
        count = -1
        break
    elif B % 2 == 0:
        B //= 2
        count += 1
    elif B % 10 == 1:
        B //= 10
        count += 1
print(count)