[Leetcode] 279. Perfect Squares

문제

 

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

Perfect Squares - LeetCode

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.

 

Example 1:

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

Example 2:

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

 

 

문제풀이 코드

# Dp 풀이 방식
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [inf for _ in range(10001)]
        dp[0] = 0
        ps = []
        
        i = 1
        while i*i <= n:
            ps.append(i*i)
            i += 1
        
        for i in range(1, n + 1):
            for s in ps:
                if i < s:
                    break
                dp[i] = min(dp[i], dp[i-s] + 1)  
        return dp[n]

# Bfs 풀이 방식
class Solution:
    def numSquares(self, n: int) -> int:
        if n < 2:
            return n

        perfect_square = []
        i = 1
        while i * i <= n:
            perfect_square.append(i*i)
            i += 1
        
        check = {n}
        count = 0
        while check:
            count += 1
            temp = set()
            for num in check:
                for square in perfect_square:
                    if num == square:
                        return count
                    if num < square:
                        break
                    temp.add(num - square)
            check = temp
        return count

다이나믹 프로그래밍 풀이

1. 0은 만들 수 있는 수가 없고, 1은 1로 만들 수 있고, 2는 1+1로 만들 수 있고, 3은 1+1+1로 만들 수 있고, 4는 4로 만들 수 있다.

2. 식으로 변형하면 dp[0] = 0, dp[1] = 1, dp[2] = 2, dp[3] = 3, dp[4] = 1이 된다.

3. 예를 들어 구해야되는 수가 7이면, 7 = 4 + 3(1 + 1 + 1)이 되기 때문에 dp[7-4] + 1이 되게 된다.

4. 이를통해 점화식을 구하면 dp[i] = min(dp[i], dp[i-제곱수] + 1)가 된다.

5. n 보다 작은 모든 제곱수를 담은 리스트를 만들고 1 ~ n까지 반복문을 돌면서

6. s가 i보다 작을때만 dp[i]를 초기화 해준다.(i = 3인데 제곱수가 4가나오면 계산할 수 없음)

7. 반복문이 종료되면 dp[n]을 반환한다.

 

BFS 풀이

1. 다이나믹 프로그래밍과 동일하게 n보다 작은 모든 제곱수를 리스트에 담아준다.

2. 체크할 수를 딕셔너리 형태로 저장(이 후 연산후 중복된 값이 들어가지 않도록하기위함)

3. 반복문을 돌때마다 카운트를 1씩 증가시켜준다.

4. check에 있는 수에 모든 제곱수를 빼준다.

5. 연산된 숫자들이 담긴 집합을 check에 담아준다.

6. 반복하면서 check에 제곱수가 들어가있다면 현재 count를 반환한다.