[LeetCode] 991 | Broken Calculator | Python

---

문제 링크: https://leetcode.com/problems/broken-calculator/

---

문제

There is a broken calculator that has the integer startValue on its display initially. In one operation, you can:

• multiply the number on display by 2, or
• subtract 1 from the number on display.

Given two integers startValue and target, return the minimum number of operations needed to display target on the calculator.

---

조건

• 1 <= x, y <= $10^9$

---

내 풀이

(1) startValue를 target으로 만드는 것은, (2) target을 startValue로 만드는 것과 그 횟수가 동일하다.

이렇게 하는 이유는 (1)방법대로 하면 언제 1을 빼고 2를 곱해야하는지 모르지만, (2)방법대로 하면 짝수일 때 2를 나누고, 홀수일 때 1을 더하면 되기 때문이다.

---

코드

class Solution:
    def brokenCalc(self, startValue: int, target: int) -> int:
        ans = 0
        
        while target > startValue:
            ans += 1
            if target % 2:
                target += 1
            else:
                target //= 2
            
        return ans + startValue - target