Problem link

https://leetcode.com/problems/broken-calculator/

Problem Summary

startValue 와 target이 주어질 때 startValue를 target으로 만드는 최소 연산 횟수를 구하는 문제.
연산은 2를 곱하는 것과 1을 빼는 것이 있다.

Solution

문제를 그대로 풀면 꽤 tricky 한데 반대로 생각해보면 쉽게 풀린다.
즉, target을 startValue로 만드는 최소 횟수를 구하면 된다. 대신 연산은 2을 나누는 것과 1을 더하는 것으로 바꾸면 된다.

이렇게 되면 만약 target이 홀수이면 1을 더하는 방법밖에 없게 되고 다른 경우의 수는 고려하지 않아도 된다. target이 짝수일 때는 무조건 나누는 것이 최소인데, 당연하게도 1씩 더해봐야 바로 나눠서 startValue에 가까워지는게 유리하기 때문이다. ((x + 1 + 1) // 2 == x // 2 + 1) 처럼 바로 나누는 것이 무조건 이득이다.
한가지 예외사항으로는 startValue가 더 큰 경우가 있을텐데, 이는 startValue - target으로 한번에 구해서 리턴할 수 있다. (커지려면 1씩 증가하는 방법밖에 없다.)

Source Code

class Solution:
    def brokenCalc(self, startValue: int, target: int) -> int:

        def solve(startValue, target):
            if startValue == target:
                return 0
            if startValue > target:
                return startValue - target

            if startValue < target:
                if target % 2 == 0:
                    return 1 + solve(startValue, target // 2)
                else:
                    return 1 + solve(startValue, target + 1)

        return solve(startValue, target)