[알고리즘/그리디] 16953번 : A → B - python

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

16953번: A → B

 

---

• 문제
• 소요시간: 20분(실패)

---

• 설계하기(접근방법) 

1. 입력받기

2. 알고리즘 해석

전부 탐색할 수도 있지만

숫자가 주어졌으니 역순으로 해결해나갈수 있다

 

1) 끝자리가 1인 경우, 10으로 나누어 1을 제거해준다

2) 나머지 2로 나뉘는 경우, 2로 나누어준다

 

1),2)를 진행하며 cnt ++를 한다

 

만약 while문 내에 숫자의 변화가 없는 경우, 그것은 숫자를 만들 수 없는 경우기 때문에 변화검사를 해주고 -1을 출력한다

 

3.출력하기

cnt를 출력한다

 

 

---

• 코드(출력)

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

while (b != a):
    temp = b
    cnt += 1
    if b % 2 == 0:
        b //= 2
    elif b % 10 == 1:
        b //= 10
    if temp == b:
        cnt = -1
        break


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

 

---

• 얻어갈 부분

1. 역순으로 할 수 있다는 점을 고려하지 못해 시간이 오래 걸렸다.