Leetcode 650. 2 키 키보드 2 손가락 키보드 문제 풀이 보고서

이 문 제 는 숫자 N 으로 바 꿀 수 있 습 니 다. 처음에 K = 1, C = 0 을 준 다음 에 두 가지 조작 만 할 수 있 습 니 다. 1, K = K + C (paste) 2, C = K (copy all) 는 어떻게 조작 하면 N 을 가장 빨리 얻 을 수 있 는 지 물 었 습 니 다.
N > 1 시, 사실 이 문 제 는 N 을 M 개의 숫자의 곱 으로 분해 하고 M 개의 숫자의 합 이 가장 작다.
예 를 들 어: 2 = 1 * 1 = 2 3 = 1 * 1 * 1 = 3 4 = 2 * 2 = 1 * 1 * 1 = 4 등등 그러면 가장 빨리 한 개 수 를 말 해서 N 개의 질 수로 분해 하 는 것 과 어 떡 하 죠?

Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:

Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
Paste: You can paste the characters which are copied last time.
Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.

Example 1:
Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.
Note:
The n will be in the range [1, 1000].

두 가지 방법 을 주 었 습 니 다. 첫 번 째 는 다른 사람 이 쓴 것 을 보고 두 번 째 는 제 가 만 든 것 입 니 다. 속도 가 별로 차이 가 없 는 것 같 습 니 다.
첫 번 째 는 주로 어 릴 때 부터 어른 이 될 때 까지 탐색 하 는 것 이 고, 가능 한 한 작은 숫자 로 제거 하면 된다.
대신 간결 해법: 39ms

class Solution(object):
    def minSteps(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = 0
        for i in range(2, n+1):
            while (n % i == 0):
                res += i
                n /= i
        return res

DP 재 귀판 36ms
먼저 두 숫자의 하위 문제 로 바 뀌 었 고 A = B * C 와 B + C 가 가장 작 았 다. 즉, 이 두 숫자의 합 이 가장 작은 것 을 말한다.cache 를 추가 하 는 것 을 기억 하 세 요.

class Solution(object):
    import math
    def helper(self, n):

        """
        :type n: int
        :rtype: int
        """
        if n in self.cache:
            return self.cache[n]
        for i in range(int(math.sqrt(n)),1,-1):
            if n % i == 0:
                a = self.helper(i)
                b = self.helper(n / i)
                self.cache[n] = a + b
                return a+ b
        self.cache[n] = n
        return n


    def minSteps(self, n):
        """
        :type n: int
        :rtype: int
        """
        self.cache = dict()
        self.cache[1] = 1
        if n == 1:
            return 0
        return self.helper(n)