[LeetCode] DP - 279. Perfect Squares (feat. 라그랑주의 네제곱수)

문제

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 <= 104

코드

/**
 * @param {number} n
 * @return {number}
 */

var numSquares = (n) => {
    // 라그랑주의 네 제곱수 정리
    // : 모든 양의 정수는 많아야 4개의 제곱수의 합이다.

    // 4^n * (8n + 7)은 반드시 4개의 제곱수로 나타낼 수 있음
    while(n % 4 === 0) {
        n /= 4;
    }

    // 4^n * (8n + 7)은 반드시 4개의 제곱수로 나타낼 수 있음
    if(n % 8 === 7) {
        return 4;
    }

    // 제곱수인 경우 1을 반환
    if(isSquares(n)) {
        return 1;
    }

    for(let i = 1; i * i < n; i++) {
        // n에서 제곱수를 뺀 값이
        // 제곱수인 경우 => 제곱수 + 제곱수로 나타나는 경우
        if(isSquares(n - (i * i))) {
            return 2;
        }
    }

    // 위 조건이 아닌 경우 무조건 3개로 나눌 수 있음
    return 3
}

function isSquares(n) {
    const rootN = Math.floor(Math.sqrt(n));
    
    return n === rootN * rootN;
}

/**
 * 3 => 1^2 + 1^2 + 1^2;
 * 4 => 2^2
 * 5 => 2^2 + 1^2
 * 6 => 2^2 + 1^2 + 1^2
 * 7 => 2^2 + 1^2 + 1^2 + 1^2
 * 8 => 2^2 + 2^2
 * 9 => 3^2
 * 10 => 3^2 + 1^2
 * 11 => 3^2 + 1^2 + 1^2
 * 12 => 3^2 + 1^2 + 1^2 + 1^2
 * 13 => 3^2 + 2^2
 * 14 => 3^2 + 2^2 + 1^2
 * 15 => 3^2 + 2^2 + 1^2 + 1^2
 * 16 => 4^2
 */