[node.js] 제곱수의 합 ( 백준 1699번 )

요즘 DP 문제만 주구장창 풀고 있는데, DP를 푸는 요령은 이렇다.
먼저 DP[n]이 의미하는 것이 무엇인지 찾는다.
이 문제에는 DP[n]의 정의는, n을 만들기 위해서 필요한 최소 제곱수 항이었다.
DP[n]을 그러면 숫자들의 나열로 생각한다. ( 이 문제는 합이기 때문에 덧셈의 나열로 생각하면 된다. )
거기서 마지막이 무엇인지 생각한다.
이 문제에서는 당연히, n의 제곱근이 될 것이다.
그렇다면 우리가 알 수 있는 게 생긴다.

DP[n - 마지막 값의 제곱] + 1이 DP[n]이라는 점화식이다.

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on("line", (line) => {
    main(line);
    rl.close();
}).on("close", () => process.exit());

/**
 *
 * @param {string} line
 */
const main = (line) => {
    const numbers = new Array(Number(line) + 1).fill(0).map((el, i) => i);
    const DP = [0, 1];

    for (let i = 1; i < numbers.length; i++) {
        DP[i] = DP[i - 1] + 1;
        for (let j = 1; j <= Math.sqrt(i); j++) {
            if (i - j ** 2 >= 0 && DP[i - j ** 2] + 1 < DP[i]) {
                DP[i] = DP[i - j ** 2] + 1;
            }
        }
    }
    console.log(DP[numbers.length - 1]);
};