[JavaScript] 백준 1699 제곱수의 합 (JS)

제곱수의 합

📚 문제 설명

자연수 N은 그보다 작은 제곱수들로 나타낼 수 있다.

예를 들어 11= 3^2 + 1^2 + 1^2 (3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데,
11의 경우 11 = 2^2 + 2^2 + 1^2 + 1^2 + 1^2 (5개 항)도 가능하다.

자연수 N이 주어질 때 만들 수 있는 제곱수 항의 최솟값을 구하여라.

👨🏻‍💻 풀이 과정

가장 먼저 들었던 생각은 Math.floor(Math.sqrt(N))을 구하여 빼는 방법이다.
이 방법을 쓰면 가장 큰 제곱 수를 구해서 빼줄 수 있다.
그런데 이렇게하면 43에서 반례가 생기는데 순서대로 알아보자.

가장 큰 제곱 수부터 계산했을 때.
43 = 36 + 4 + 1 + 1 + 1 (항의 갯수 : 5)

그런데 43의 숫자는 아래와 같이 될 수도 있다.
43 = 25 + 9 + 9 (항의 갯수 : 3)

따라서 가장큰 제곱수부터 계산하는 방식을 잘못되었다.

점화식

0 < i <= N 이고 1 <= j <= Math.sqrt(i) 일 때,
점화식을 아래와 같다.
dp[i] = Math.min(dp[i], dp[i - (j ** 2)] + 1)

이 점화식을 예시와 함께 간단하게 설명하면
dp[43]을 구하기 위해 dp[43 - 36], dp[43 - 25] ......dp[43 - 1] 중의 최솟값을 찾는 것이다.

전체 풀이

    let fs = require("fs");
    let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = parseInt(input.shift());

    let dp = Array.from({length: N + 1}, (value, index) => index);

    for (let i = 4; i <dp.length; i++) {
        for (let j = 1; j <= Math.sqrt(i); j++) {
            dp[i] = Math.min(dp[i], dp[i - (j ** 2)] + 1);
        }
    }
    console.log(dp[N]);

🧐 후기

그동안 React 공부를 하다가 오랜만에 알고리즘 문제들을 푸니 색다른 느낌이 든다.
빨리 React 공부 내용도 정리해서 블로그에 업로드해야겠다.