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

description

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

example

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

풀이

코드

class Solution:
    def numSquares(self, n: int) -> int:
        square = [i**2 for i in range(1, math.floor(n**0.5)+1)]
        dp = [0] * (n+1)
        dp[1] = 1
    
        for num in square :
            dp[num] = 1
        for i in range(2, n+1) :
            if dp[i] == 0 :
                squares = [num for num in square if num < i]
                possible = [dp[i-idx] for idx in squares]
                dp[i] = min(possible) + 1
        return dp[n]

결과

Runtime: 3096 ms, faster than 55.44% of Python3 online submissions for Perfect Squares.
Memory Usage: 14.2 MB, less than 93.60% of Python3 online submissions for Perfect Squares.

설명

먼저 1부터 루트 n까지 perfect square number들의 배열을 구한다. 그리고 인덱스를 1부터 생각하는 게 편하기 때문에 n+1의 사이즈를 가지는 배열을 선언하고 0으로 초기화한다. 이때 인덱스 1의 값은 1이 된다.

아까 구한 square number들을 순회하면서 value를 자기자신 1로 수정한다. 이후 2부터 n까지 순회하면서 만약 dp[i]이 0이라면 sqaure 넘버가 아니므로, 값을 구해야 한다.

일단 인덱스 i보다 작은 스퀘어 넘버의 배열을 구하고, 각각의 값만큼 뺀 dp[i-idx]를 구한다. 왜냐하면 스퀘어 넘버만큼의 간격이라면 1차이가 나기 때문이다. 구한 배열에서 가장 값이 적은 애를 데려와 거기에 +1을 한 값이 dp[i]가 된다.