650. 2 Keys Keyboard

[zeikar]

Problem link

https://leetcode.com/problems/2-keys-keyboard/

Problem Summary

복사, 붙여넣기만 가능한 키보드에서 특정 길이를 만드는 최소 횟수를 구하는 문제

Solution

일단 간단히 DP로 풀리긴 한다. dp[i][j] = i길이를 j만큼 붙여넣어 만들때 최소 횟수. O(n^2)

그런데 여기서 수학적으로 접근하면 O(n)으로 가능하다.
자세한건 에디토리얼 참고.

Source Code

class Solution:
    def minSteps(self, n: int) -> int:

        @cache
        def getMinSteps(l, copy):
            if l > n:
                return 987654321
            if l == n:
                return 0

            if copy == 0:
                copy = l
                return getMinSteps(l + copy, copy) + 2

            return min(getMinSteps(l * 2, l) + 2, getMinSteps(l + copy, copy) + 1)

        return getMinSteps(1, 0)