279. Perfect Squares

문제

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

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

접근

#dp #수학

perfectSq : n이하의 제곱수를 모아둔 배열.
dp[n] : 주어진 값이 n일때의 제곱수의 최소 개수.

n이하의 모든 자연수를 순회하며 해당 로직을 수행한다:
1. i의 제곱수를 구한다(i_sq)
1-1. i의 제곱이 n이하라면 perfectSq에 추가하고, dp[i_sq] = 1로 한다.
1-2. perfectSq의 값을 ps로 모두 꺼내어 dp[i]와 비교한다. 이 때, i가 ps보다 작으면 루프에서 탈출한다. (i-ps>0 이어야 하기 때문)
1-2. dp[i] = min(dp[i], 1+dp[i-ps])
기존의 dp[i]와, ps가 더해진 값(+1)을 비교한다.

코드

class Solution:
    def numSquares(self, n: int) -> int:
        # n이하의 모든 제곱수를 저장.
        perfectSq = []
        
        # dp.
        dp = [inf] * (n+1)
        
        for i in range(1,n+1):
            
            # i의 제곱을 구하고, dp[i*i] =1 로 세팅.
            # i*i이 n이하라면 perfectSq에 저장한다.
            i_sq = pow(i,2)
            if i_sq <= n:
                perfectSq.append(i_sq)
                dp[i_sq] = 1
            
            # dp 연산
            for ps in perfectSq:
                # i는 i를 구성하기 위한 완전제곱수보다 작아야한다.
                if i<ps: break
                
                dp[i] = min(dp[i],1+dp[i-ps])
                # dp[i] = min(dp[i],dp[ps]+dp[i-ps])와 같다 (dp[ps]=1)

        return dp[n]

효율성

Runtime: 6711 ms, faster than 11.06% of Python3 online submissions for Perfect Squares.
Memory Usage: 13.9 MB, less than 88.62% of Python3 online submissions for Perfect Squares.