[LeetCode] 279. Perfect Squares

Problem

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: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

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

Constraints:

• 1 <= n <= 10^4

---

Solution

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j * j <= i; j++)
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        return dp[n];
    }
}

Explanation

• n의 값에 따라 numSquares(n)을 실행한 결과로 반환해야 하는 값은 다음과 같다. (0은 계산 편의상 추가)

|n|numSquares(n)|equal to| |:—:|:—:|:—:| |0|0|0| |1|1|numSquares(1 - 1 * 1) + 1| |2|2|numSquares(2 - 1 * 1) + 1| |3|3|numSquares(3 - 1 * 1) + 1| |4|1|min(numSquares(4 - 1 * 1) + 1, numSquares(4 - 2 * 2) + 1)| |5|2|min(numSquares(5 - 1 * 1) + 1, numSquares(5 - 2 * 2) + 1)| |…|…|…| |9|3|min(numSquares(9 - 1 * 1) + 1, numSquares(9 - 2 * 2) + 1, numSquares(9 - 3 * 3) + 1)| |10|4|min(numSquares(10 - 1 * 1) + 1, numSquares(10 - 2 * 2) + 1, numSquares(10 - 3 * 3) + 1)| |…|…|…| |16|4|min(numSquares(16 - 1 * 1) + 1, numSquares(16 - 2 * 2) + 1, numSquares(16 - 3 * 3) + 1, numSquares(16 - 4 * 4) + 1)| |17|5|min(numSquares(17 - 1 * 1) + 1, numSquares(17 - 2 * 2) + 1, numSquares(17 - 3 * 3) + 1, numSquares(17 - 4 * 4) + 1)|

• 가장 작은 square값인 1로 나눌 수 있는 n의 값이 증가하여 두 번쨰로 작은 square값인 4로 나눌 수 있는 값이 되면 numSquares(n)의 값은 두 square으로 나눈 값 중 작은 값을 선택해야한다. 즉, n을 나눌 수 있는 square값의 개수가 증가할 때마다 선택지가 증가하는 셈이다.

• 위의 표는 n이 0일때 부터 시작하여 numSquares(n)의 반환 값을 누적 기록해 나가야 최종 반환 값을 구할 수 있다. 이를 위해 길이가 n + 1인 배열 dp를 선언한다.

• 계산이 올바르게 동작하도록 배열 dp의 요소를 정수형의 최대값으로 채우고 첫 번째 요소에 계산에 필요한 0을 할당해준다.

  int[] dp = new int[n + 1];
  Arrays.fill(dp, Integer.MAX_VALUE);
  dp[0] = 0;
  

• n을 나눌 수 있는 square값의 개수가 증가할 때마다 선택지가 증가하도록 for반복문을 작성한다.

• 배열 dp의 마지막 요소를 반환한다.

  for (int i = 1; i <= n; i++)
    for (int j = 1; j * j <= i; j++)
        dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
  return dp[n];