[Greedy] 16953 A->B

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

16953번: A → B

# 2022.12.31
import sys
input = sys.stdin.readline

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

cnt = 0

while (1):
    cnt+=1
    tmp = b

    if a==b:
        print(cnt)
        break
    if b%10==1:
        b//=10
    elif b%2==0:
        b//=2
        
    if tmp ==b:
        print("-1")
        break

a->b 로 푸는 것보다는 b->a로 생각하는게 더 쉽다

 

1. a==b가 될 때까지 cnt+=1

2. b의 제일 오른쪽 1을 빼는게 더 연산 횟수가 적다

3. 아니면 b를 2로 나누기

4. 오른쪽 1을 빼는 연산 or 2로 나누는 연산 둘 다 수행하지 못하면? -> 답이 없다!  -> -1을 출력

 

key point!

tmp에 계속 저장을 하면서 비교를 해주는 이유는 연산이 수행되었는지 확인하는 용도

---

틀린 코드

# 2022.12.31
import sys
input = sys.stdin.readline

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

cnt = 0

while (a<=b):
    cnt+=1

    if a==b:
        print(cnt)
        break
    if b%10==1:
        b//=10
    elif b%2==0:
        b//=2
    else:
        print("-1")
        break

제일 밑의 부분을 else로 바꾸면 왜 안될까?

논리적으로 두 연산 모두 수행하지 못하면 답이 없기때문에 -1을 출력한다는 점은 동일한데 ...

[수정]

이렇게 하면 안되는 이유는 

4 42일때,

42->21->2
이렇게 계산되는데

a<=b에서 걸려서 바로 while문을 탈출하게 된다..

 

논리적으로 틀린 코드임..