279. Perfect Squares

Perfect Squares - LeetCode

1. DP 풀이

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0] * (n + 1)
        for i in range(1, int(math.sqrt(n)) + 1):
            dp[i * i] = 1
        for i in range(1, n + 1):
            if dp[i]:
                continue
            else:
                temp = int(math.sqrt(i))
                dp[i] = dp[temp] + dp[i - temp]
                for j in range(1, temp + 1):
                    dp[i] = min(dp[i], dp[j * j] * (i // (j * j)) + dp[i % (j * j)])
        return dp[n]

실행시간을 보면 아무리 생각해봐도 최적화가 필요한 것 같다.

2. DP 풀이(최적화)

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float("inf")] * (n + 1)
        dp[0] = 0
        dp[1] = 1
        for i in range(2, n + 1):
            j = 1
            while i >= j * j:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1
        return dp[n]

30퍼센트 정도 시간을 줄였다. 테스트 케이스가 원래 좀 빡빡한 것 같다.

3. BFS

from collections import deque


class Solution:
    def numSquares(self, n: int) -> int:
        q = deque([(n, 0)])
        set1 = {n}
        while q:
            cur_num, cur_level = q.popleft()
            if cur_num == 0:
                return cur_level
            j = 1
            while cur_num >= j * j:
                temp = cur_num - (j * j)
                if temp not in set1:
                    set1.add(temp)
                    q.append((temp, cur_level + 1))
                j += 1

놀랍게도 BFS로 풀 수 있다.

노드의 값이 0이 될 때의 높이가 우리가 원하는 값이 된다.

이때 만든 노드를 중복해서 만들지 않도록 집합으로 관리한다.

 

지식이 늘었다.