💡문제접근
- 계산 방법을 이용해서 접근했다. A에서 K로 가는 방식은 매우 복잡하기 때문에 K에서 A로 가는 역방향 접근 방식을 선택했다.
- 문제에서 주어진 연산 방식을 역방향 연산 방식을 적용하면 다음과 같이 바꿀 수 있다.
①. 연산1 : 정수 A에 1을 더한다. → 정수 K에서 1을 뺀다.
②. 연산2 : 정수 A에 2를 곱한다. → 정수 K를 2로 나눈다.
💡테스트케이스1
입력
7 77
출력
7
- 77 → 76 → 38 → 19 → 18 → 9 → 8 → 7이어야 한다. 이 때, 8은 2의 배수로 2로 나누게 된다면 7이 나올 수가 없다. 이 부분을 어떻게 처리해줘야할지 고민이 많았는데 다른 테스트케이스를 보고 좀 끼워 맞췄다.
💡테스트케이스2
입력
5 10
출력
1
- 10 → 5로 1번의 연산 과정을 거치면 되는데 이 때, K = A×2가 성립했다. 이걸 이용해서 K가 2의 배수이면서 2×A보다 크거나 같은 값이어야 실행할 수 있도록 작성했더니 AC를 받았다. 솔직히 말해서 왜
K ≥ A×2이어야 하는지는 잘 모르겠다.
💡코드(메모리 : 30616KB, 시간 : 84ms)
import sys
A, K = map(int, sys.stdin.readline().strip().split())
cnt = 0
while True:
if A == K:
break
if K % 2 == 0 and K >= A*2:
K //= 2
cnt += 1
else:
K -= 1
cnt += 1
print(cnt)💡소요시간 : 17m
🐢