[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⁴

Idea

주어진 수를 제곱으로 된 수의 합으로 구성할 때, 가장 적은 개수의 수를 사용하는 경우를 구하는 문제다.

우선 제곱을 매번 구하지 않고 squares라는 array에 미리 저장을 해놨다. n의 범위가 10⁴에 불과하므로 100까지만 계산하면 된다.

이후 1부터 n까지 최소의 수를 순서대로 계산한다. 이 때 얻어진 값은 dp에 저장해 다음 연산에 활용한다. 만약 주어진 값이 제곱으로 확인되면 값이 1이 된다. 그렇지 않을 경우는 제곱을 index로 하여 순차적으로 최소 가지수가 몇인지 확인한다. dp를 이용해 제곱을 뺀 수의 최소 가지수를 얻고 이에 1을 더한 값을 계산해 가장 적은 값을 해당 값의 최소 가지수로 저장한다.

n까지 연산이 끝났으면 dp에서 값을 확인해 결과로 리턴한다.

Solution

class Solution {
    public int numSquares(int n) {
        int squareIndex = 0;
        int[] dp = new int[n+1];
        int[] squares = new int[101];

        for (int i=1; i <= 100; i++)
            squares[i] = i * i;

        for (int i=1; i <= n; i++) {
            if (i == squares[squareIndex+1]) {
                dp[i] = 1;
                squareIndex++;
                continue;
            }
   
            int least = Integer.MAX_VALUE;
            for (int j=squareIndex; j > 0; j--) {
                least = Math.min(least, 1 + dp[i - squares[j]]);
            }
            dp[i] = least;
        }

        return dp[n];
    }
}

Reference

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