279. Perfect Squares ★★★

279. Perfect Squares

 

# 완전 제곱수의 합이 n 이 되는 요소 개수 찾기

# 그런데 그 요소 개수가 최대한 적어야 해서.

# 제곱수는 큰수로 이뤄저 있어야 하므로, 큰수부터 검색하는것이..

# DP 또는 BFS 로 풀수 있음

 

 

1. Dynamic Programming (DP) 풀이

 

 

예제)

class Solution:
    def numSquares(self, n: int) -> int:
        """
        문제 설명:
        정수 n을 완전 제곱수들의 합으로 표현할 때, 필요한 최소 항의 개수를 구하는 문제.
        완전 제곱수는 1, 4, 9, 16과 같은 수를 의미합니다.
        """

        # DP 배열 초기화
        # dp[i]는 숫자 i를 완전 제곱수의 합으로 표현할 때 필요한 최소 항의 개수
        dp = [float('inf')] * (n + 1)
        dp[0] = 0  # 숫자 0은 완전 제곱수를 사용하지 않아도 됨

        # 숫자 1부터 n까지 DP 배열을 채움
        for i in range(1, n + 1):
            j = 1
            # i보다 작거나 같은 모든 완전 제곱수 j^2 탐색
            while j * j <= i:
                # 점화식: dp[i] = min(dp[i], dp[i - j^2] + 1)
                # dp[i - j^2]는 (i에서 j^2를 뺀 나머지 숫자)를 표현하는 최소 항의 개수
                # +1은 j^2를 사용한 항을 추가
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1

        # dp[n]은 숫자 n을 표현할 때 필요한 최소 항의 개수
        return dp[n]

# 테스트
sol = Solution()
print(sol.numSquares(12))  # 출력: 3 (4 + 4 + 4)
print(sol.numSquares(13))  # 출력: 2 (4 + 9)

 

2. Breadth-First Search (BFS) 풀이

아이디어:

1. 그래프 탐색처럼 접근합니다.
2. 숫자 n에서 시작하여, 완전 제곱수를 빼는 과정을 노드 탐색처럼 수행합니다.
3. 각 단계에서 방문한 노드는 해당 숫자를 만들기 위한 최소 항의 개수를 의미합니다.

알고리즘:

1. 큐를 사용하여 현재 숫자와 사용된 항의 개수를 저장합니다.
2. BFS를 진행하며 현재 숫자에서 가능한 모든 완전 제곱수를 뺀 값을 큐에 추가합니다.
3. 숫자가 0이 되면 탐색을 종료하고 사용된 항의 개수를 반환합니다.

class Solution:
    def numSquares(self, n: int) -> int:
        """
        BFS와 DP 유사 로직:
        - BFS로 계층적으로 탐색하며 최소 항의 개수를 찾음
        - visited를 사용해 중복 계산 방지
        """
        # BFS를 위한 큐 초기화
        queue = deque([(n, 0)])  # (현재 숫자, 사용한 항의 개수)
        visited = set()  # 중복 계산 방지를 위한 방문 체크
        visited.add(n)
        
        while queue:
            num, steps = queue.popleft()

            # 현재 숫자에서 가능한 모든 완전 제곱수를 뺌
            j = 1
            while j * j <= num:
                next_num = num - j * j
                # 목표 숫자가 0이 되면 최소 항의 개수를 반환
                # 숫자가 0에 도달했다는 것은 숫자 n을 완전 제곱수들의 합으로 완전히 분해했음을 의미함
                # 이때 첫 번째로 0에 도달한 경로가 BFS의 특성상 최소 항을 보장
                if next_num == 0:
                    return steps + 1  # 목표 숫자 0에 도달하면 종료
                if next_num not in visited:
                    visited.add(next_num)  # 방문하지 않은 숫자만 큐에 추가
                    queue.append((next_num, steps + 1))
                j += 1