279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

반복문 n 개 중첩이 떠올라서... 루션이 불렀읍니다.

DP Solution

Solution 1: Runtime: 4488 ms - 32.52% / Memory Usage: 14.3 MB - 83.32%

class Solution:
    def numSquares(self, n: int) -> int:
        ## RC ##
        ## APPROACH : DP ##
        
		## TIME COMPLEXITY : O(N^2) ##
		## SPACE COMPLEXITY : O(N) ##
    
        if( n < 3) : return n
        square_nums = [i**2 for i in range(0, int(math.sqrt(n))+1)]
        
        dp = [float('inf')] * (n+1)
        dp[0] = 0
        for i in range(1, n+1):
            for square in square_nums:
                if(i < square): break
                dp[i] = min(dp[i], dp[i-square] + 1)    # +1 is for that square we are substracting.
        return dp[-1]

루트n+1 까지의 square 값을 square_nums 에 미리 저장
float('inf'): 실수 데이터 양의 무한대

사실 잘 이해가 안됩니다...