279. Perfect Squares

[zeikar]

Problem link

https://leetcode.com/problems/perfect-squares

Problem Summary

1부터 10000까지의 수가 주어질 때 더해서 만들 수 있는 최소 제곱수의 개수를 구하는 문제.

Solution

딱 보니 전형적인 DP 문제이다. (medium 난이도는 대부분이 DP 같다...)
dp[i] = 최소 제곱수의 개수로 정의하고 j를 제곱수라고 했을 때

dp[i] = min(dp[i], dp[i - j] + 1)

시간 복잡도는 i에 대해 한번, j에 대해 한번 돌게 되므로 O (n ^ 1.5) 가 된다. (제곱수는 n ^ 0.5번만 돌면 된다) 근데 실제 제출했을 때 top down, bottom up 둘다 생각보다 느린데 알고보니 수학적으로 O(n ^ 0.5)로 풀 수 있다...

라그랑주의 네 제곱수 정리 (Lagrange's Four Square theorem) 가 존재하는데 모든 자연수는 최대 4개의 제곱수로 만들 수 있다는 정리이다. 즉 이 문제의 답은 1, 2, 3, 4 중에 하나.
또한 추가로 제곱수 정리들을 더 활용하면 수학적으로 O(n ^ 0.5)로 풀 수는 있다... 만 재미 및 참고용으로만 보자. (코딩 인터뷰때 이렇게 풀면 라그랑주의 네 제곱수 정리를 증명해야 할 것...)

Source Code

Top-Down DP (7680ms)

class Solution:
    def numSquares(self, n: int) -> int:
        squares = []
        for i in range(1, 100):
            squares.append(i * i)

        @cache
        def solve(n):
            if n == 0:
                return 0
            if n < 0:
                return 987654321

            res = 987654321
            for s in squares:
                res = min(res, solve(n - s) + 1)

            return res

        return solve(n)

Bottom-Up DP (2930ms)

from math import sqrt


class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0]
        for i in range(1, n + 1):
            dp.append(i)

        for i in range(1, int(sqrt(n))+1):
            for j in range(2, n + 1):
                if j - i * i >= 0:
                    dp[j] = min(dp[j], dp[j - i * i] + 1)

        return dp[n]

Mathematically (39ms)

class Solution:    
    def is_perfect_square(self, n):
        root = int(math.sqrt(n))
        return root*root == n

    def numSquares(self, n: int) -> int:
         # Check if n is a perfect square
        if self.is_perfect_square(n):
            return 1
        
        # Check the sum of two squares theorem by trying every square less than n
        for i in range(1, int(n**0.5) + 1):
            if self.is_perfect_square(n - i*i):
                return 2
        
        # The four-square and three-square theorems - Check if the number can be expressed as the sum of three squares
        # This checks if it's NOT of the form 4^a(8b + 7) for any non-negative integers a and b
        while n % 4 == 0:
            n /= 4
        if n % 8 == 7:
            return 4

        return 3