Perfect Squares

어떤 정수가 주어졌을 때, 제곱이 되는 수로 어떤 합이 결정되는지 구하는 문제

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

import math


class Solution:
    def numSquares(self, n: int) -> int:
        currentValues = { n }
        count = 0
        
        while currentValues:
            nextValues = set()
            
            for currentValue in currentValues:
                for i in range( 1, int( math.sqrt( currentValue ) ) + 1 ):
                    remainValue = currentValue - i * i
                    
                    if not remainValue:
                        return count + 1
                    elif remainValue > 0:
                        nextValues.add( remainValue )
                        
            currentValues = nextValues
            count += 1
        
        return 0