650.2 Keys Keyboard - Leetcode

650. 2 Keys Keyboard

My code

base case에서 부터 시작하여 모든 case에 대해 call해보고, 조건을 만족하는 경우 중에 최소값 저장.

base case의 경우는
‘AA’ 에서 copy = ‘A’ 를 가지고 있고, 현재까지 사용한 step은 2번.
모든 case에 대해 시도해보고, 정확히 n번의 ‘A’가 나올 모든 경우중 step이 가장 적은 경우를 ans로 한다.
비효율적이지만, 통과는 가능하다.

In [12]:

class Solution(object):
    def __init__(self):
        self.ans = 1e10
    def minSteps(self, n):
        """
        :type n: int
        :rtype: int
        """
        assert n >= 1, "error"
        if n == 1: return 0
        if n == 2: return 2 
        
        def f(state, copy, step ):
            if state > n: return 
            if state == n:
                self.ans = min(self.ans, step)
            # copy all and paste
            f(state=state + state, copy=state, step=step + 2)   
            # just paste
            f(state=state + copy, copy=copy, step=step + 1)
            
        f(state=2, copy=1, step=2)
        return self.ans

sol = Solution()

In [13]:

sol.minSteps(n=8)

6

Runtime: 612 ms, faster than 26.85% of Python online submissions for 2 Keys Keyboard.

Another Code (more efficient)

남은 ‘A’ 수 만큼에 대해 greedy하게 call 하며 최소값을 찾아준다.

‘A’의 수가 딱 맞아 떨어져야함을 기억하자.
n 에서 시작하여, integer factorization을 시도.

i 로 factorization되었다면, n // i (i로 나눈 몫) 개수의 ‘A’에 대해
copy all 하고, i 번 paste 하는 greedy choice임을 의미한다.
따라서, f(n) = f(n//i) + i if n % i == 0 와 같은 recursion을 통해 답을 구한다.
여기서 i는 소인수분해 factor.

예를 들면, 125 % 5 = 0 (5로 나누어 떨어짐, 즉 integer factorization 성공).
따라서, 이때는 125 // 5 = 25개의 ‘A’에 대해 5번 copy하는것이 최고의 선택임을 알수있고, 25개의 ‘A’ 에 대해 또 다시 recursion 해나감으로써 답을 구한다.

이 코드가 아름다운 점은 수식이 매우 깔끔해서이다.
자기 자신으로 소인수분해 될때 i = n 이어서n // n = 1이 된다. 그 결과, f(n) = f(1) + i = n 이 된다. 이 말은, 소인수 분해가 되지 않을때는 남아있는 A갯수를 그대로 return한 것인데 그게 답과 일치한다.

예를 들면, 소수로서 7개의 ‘AAAAAAA’는 초깃값 ‘A’ 로부터 copy를 한번하고, 6번 paste해서 7번의 step을 해야 ‘AAAAAAA’이 된다.

즉, 이 문제는 소인수분해(integer fatorization)를 해보고, 1을 제외한 소인수(factor)들의 합을 구하는 것과 같다.

In [14]:

class Solution(object):
    def minSteps(self, n):
        if n == 1: return 0
        for i in range(2, n+1):
            if n % i == 0:
                return self.minSteps(n // i) + i

In [21]:

sol = Solution()
sol.minSteps(516)

50

Runtime: 12 ms, faster than 98.15% of Python online submissions for 2 Keys Keyboard.