Leetcode【279、343】

문제 설명: [BFS, Math] 279.Perfect Squares
문제 해결 방법:
이 문제는 정정수 n을 주고 이를 제곱수 가산인자로 분해하여 분해된 인자를 가장 적게 하는 것이다.
이 문제는 실제로Leetcode[DP, BFS]와 322.Coin Change는 비슷합니다.우리는 <=n의 제곱수 인자를 동전 종류수로 하고 n을 바꿔야 할 잔돈으로 생각하면 같은 방법인 DP와 BFS를 사용하여 해답을 구할 수 있다.
메서드 1(DP, TLE):
Letcode 322와 유사하게 동적 기획을 사용하고 시간 복잡도 O(n*sqrt(n))를 사용하지만 DP 방법은 이 문제에서 시간을 초과했습니다. 참고 코드는 다음과 같습니다.
Python3 구현:

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [i for i in range(n + 1)]  #   dp     dp[i]=i
        for i in range(2, int(math.sqrt(n)) + 1):
            sqr = i * i  #    
            for j in range(sqr, n+1):
                dp[j] = min(dp[j], dp[j-sqr] + 1)  #   dp[i]     
        return dp[-1]

메서드 2(BFS, 시간 복잡도 O(n*sqrt(n), AC):
Letcode 322와 유사하며, 사용 범위가 우선이고, 시간 복잡도 O (n*sqrt (n) 이지만, AC를 사용할 수 있습니다.
Python3 구현:

class Solution:
    def numSquares(self, n: int) -> int:
        sn = []  #      
        for i in range(1, int(math.sqrt(n)) + 1):
            sn.append(i * i)
        visited = [False] * (n + 1)  #           
        visited[0] = True
        q = collections.deque()
        q.append((0, 0))
        step = 0
        while True:
            while len(q) > 0 and q[0][1] == step:
                x, _ = q.popleft()  #    
                if x == n:  #     
                    return step
                for num in sn:  #           
                    if x + num <= n and visited[x+num] == False:
                        q.append((x+num, step+1))
                        visited[x+num] = True
            step += 1
        return -1  #    

메서드 3(Math, 시간 복잡도 O(sqrt(n), AC):
사실 이 문제의 가장 좋은 해법은 하나의 수학 공식인 4제곱과 정리를 사용하는 것이다.
4제곱정리: 어떤 정수든지 네 정수를 초과하지 않는 제곱의 합을 나타낼 수 있다.
그러면 이 문제의 해법은 매우 간단해진다. 우리의 결과는 1, 2, 3, 4라는 네 가지 가능성밖에 없다.
또 하나의 중요한 추론이 있다.
4수의 제곱과 정리를 만족시키는 수 n(이곳은 4개의 수로 구성되어 있고 4개보다 작으면 안 된다)을 만족시키려면 반드시 n=(4^a)*(8b+7)을 만족시켜야 한다.
따라서 우리는 이 문제의 해법을 얻을 수 있다.

먼저 추론에 따라 n이 4개의 제곱수로 구성된 상황을 판단한다. n이 4의 배수라면 4로 나누어 입력한 n을 신속하게 축소할 수 있다.그리고 축소된 수를 8로 나누면 7이 남을지 판단하고 7이 남으면 4로 돌아간다.

n이 1개 또는 2개의 제곱수로 구성된 상황을 재판단한다. 축소된 n에 대해 폭력적으로 해독하여 하나의 수가 1개인지 2개의 제곱수로 구성된 것인지 판단할 수 있다.1 또는 2로 돌아갑니다.

그러면 나머지 한 가지 상황은 n이 3개의 제곱수로 구성된 경우 3으로 돌아가면 된다.

이 문제의 시간 복잡도는 n이 1개 또는 2개의 제곱수로 구성된 상황을 판단할 때 주로 소모된다. 시간 복잡도는 O(sqrt(n)이다.여기서 프로그래밍을 할 때 주의해야 할 점이 하나 있다. 예를 들어 n=25와 같은 것은 2(즉 3*3+4*4)를 되돌려주는 것이 아니라 1(즉 5*5)을 되돌려줘야 한다. 따라서 우리의 제곱수는 큰 (int(sqrt(n))에서 작은 (1)까지 가져와야 3*3+4*4가 먼저 나타나지 않는다는 것을 보장할 수 있다.
Python3 구현:

class Solution:
    def numSquares(self, n: int) -> int:
        while n % 4 == 0:  #(4^a)*(8b+7)   8b+7
            n //= 4
        if n % 8 == 7:  #      7，     4      
            return 4
        for i in range(int(math.sqrt(n)), 0, -1): #      1 2      ，       
            if i * i == n:  #        
                return 1
            j = int(math.sqrt(n - i * i)) #      
            if i * i + j * j == n:  #        
                return 2
        return 3  #       3      

질문 설명: [Math] 343.Integer Break
문제 해결 방법:
이 문제는 정수 n을 주고 이를 약간의 정수 덧셈 인자로 분해하여 분해된 인자의 곱셈이 가장 크도록 하는 것이다.
이 문제는 데이터 범위를 보면 DFS 소급법이 안 될 것이기 때문에 규칙을 찾을 수 있다.처음에 숫자 12를 생각했을 때 3 * 3 * 3 * 3의 분해 결과가 4 * 4 * 4(또는 2 * 2 * 2 * 2 * 2 * 2)의 분해 결과보다 크다는 것을 발견했기 때문에 분해 중의 인자는 가능한 한 4(또는 2)가 아닌 3을 많이 포함해야 한다고 추측했다.
앞의 몇 개의 숫자의 결과를 순서대로 쓸 수 있다.

dp[2]:1 * 1 = 1;

dp[3]:1 * 2 = 2;

dp[4]:2 * 2 = 4;

dp[5]:2 * 3 = 6;

dp[6]:3 * 3 = 9;

dp[7]:3 * dp[4] = 3 * 2 * 2 = 12;

dp[8]:3 * dp[5] = 3 * 2 * 3 * = 18;

dp[9]:3 * dp[6] = 3 * 3 * 3 = 27;

dp[10]:3 * dp[7] = 3 * 3 * 2 * 2 = 36;

...

이로부터 법칙을 발견할 수 있다. dp[n]:3 * dp[n-3]
따라서 n<=6에 대해 상술한 결과를 직접 반환한다.n> 6에 대해 매번 결과를 3으로 곱한 후 n을 3으로 빼고 n<=6까지 누적된 결과를 n으로 곱하면 답이다.
이런 방법의 시간 복잡도는 O(n)이고 공간 복잡도는 O(1)이다.
Python3 구현:

class Solution:
    def integerBreak(self, n: int) -> int:
        ansTo6 = [0, 1, 1, 2, 4, 6, 9]
        ans = 1
        while n > 6:
            ans *= 3  #     
            n -= 3
        return ans * ansTo6[n]  #        n

향상된 기능:
사실 상술한 절차를 개선하여 시간의 복잡도를 O(1)로 얻는 방법도 얻을 수 있다.즉, 3에 대한 나머지를 판단하고 나머지에 따라 곱셈 결과를 직접 계산한다.코드는 다음과 같습니다.

class Solution:
    def integerBreak(self, n: int) -> int:
        if n == 2: return 1
        if n == 3: return 2
        if n % 3 == 0: return 3 ** (n//3)
        if n % 3 == 1: return 3 ** (n//3-1) * 4
        if n % 3 == 2: return 3 ** (n//3) * 2