- 학부유학생 작성
Given an integer
n, return the least number of perfect square numbers that sum to
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,
16 are perfect squares while
11 are not.
Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.
Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.
1 <= n <= 104
import math from collections import deque class Solution: def numSquares(self, n: int) -> int: queue = deque([(n,0)]) while queue: num, steps = queue.popleft() for sqside in range(int(math.sqrt(num)), 0, -1): newnum = num - sqside**2 if newnum == 0: return steps+1 queue.append((newnum, steps+1))